Tanky WooRSS

POJ 3370 Halloween treats

09 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门: http://acm.pku.edu.cn/JudgeOnline/problem?id=3370


鸽笼原理的标准应用,查看鸽笼原理的资料请看这里: 传送门:http://www.wutianqi.com/?p=1267


解体报告:

// Author: Tanky Woo
// POJ 3370
#include 
using namespace std;

int ans[100001];
int use[100001];

int main()
{
    int c, n, i, j;
    while(scanf("%d %d", &c;, &n;) && (c+n))
    {
        memset(ans, 0, (n+1)*sizeof(ans[0]));
        for(i=0; i<c; ++i)
            use[i] = -1;
        int k=0;
        int flag=0;
        for(i=1; i<=n; ++i)
            scanf("%d", &ans;[i]);
        use[0] = 0;
        for(i=1; i<=n; ++i)
        {
            k = (k+ans[i])%c;
            if(use[k] != -1)
            {
                flag = 1;
                break;
            }
            use[k] = i;
        }
        if(!flag)
            puts("no sweets");
        else
        {
            printf("%d", use[k]+1);
            for(j=use[k]+2; j<=i; ++j)
                printf(" %d", j);
            printf("\n");
        }
    }
    return 0;
}