首页 > 代码库 > poj3370，抽屉原理

poj3370，抽屉原理

2024-07-16 12:50:15   219人阅读

Halloween treats
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6555 Accepted: 2417 Special Judge

Description

Every year there is the same problem at Halloween: Each neighbour is only willing to give a certain total number of sweets on that day, no matter how many children call on him, so it may happen that a child will get nothing if it is too late. To avoid conflicts, the children have decided they will put all sweets together and then divide them evenly among themselves. From last year‘s experience of Halloween they know how many sweets they get from each neighbour. Since they care more about justice than about the number of sweets they get, they want to select a subset of the neighbours to visit, so that in sharing every child receives the same number of sweets. They will not be satisfied if they have any sweets left which cannot be divided.

Your job is to help the children and present a solution.

Input

The input contains several test cases.
The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000), the number of children and the number of neighbours, respectively. The next line contains n space separated integers a1 , ... , an (1 ≤ ai ≤ 100000 ), where ai represents the number of sweets the children get if they visit neighbour i.

The last test case is followed by two zeros.

Output

For each test case output one line with the indices of the neighbours the children should select (here, index i corresponds to neighbour i who gives a total number of ai sweets). If there is no solution where each child gets at least one sweet print "no sweets" instead. Note that if there are several solutions where each child gets at least one sweet, you may print any of them.

Sample Input

4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0

Sample Output

3 5
2 3 4

Source

Ulm Local 2007


这是一道要用抽屉原理的题，我们可以用一个sum数组，记录前 i 个元素之和mod c 的结果，拿第一组数据来说明（a[i]存放糖块）


然后用mod数组存放出现该余数sum[i]时的下标，形式是mod[sum[i]]=i;

即：mod[1]=1,mod[3]=2,mod[2]=3......因为等下写代码的时候是一次对mod判断的，所以后面的mod[1]=4是不会出现的。

mod和sum的作用是：①当出现sum[i]=0时，说明从1到 i 这 i 个元素的和能被c整除，即符合题意；

②当sum[i] 的值在前面已经出现过时，说明从前面出现过的地方的下一个元素到现在的第 i 个元素的所有元      素的和能被c整除，又符合题意了。 例如，第一组数据的sum[1]=1,一直到sum[4]=1,此时sum[1]=sum[4],

说明前已经出现过余数是1了，现在又出现了，那么多从前面出现过的位置（即下标1）的下一个位置（即

下标2）到现在的第i个（即下标4）的所有元素（即下标为2,3,4的元素）之和为2+3+7=12，能被c整数，即

12%5==0.

很明确了吧，还有就是，该题不是出现无解的情况，原因是：

sum对c取余时如果等于0，我们上面已经说了是有答案的，但如果不等会0，那么sum%c=[ 1 ,c-1],一共是c-1中情况，对给出的数一共是n个，由题目可是n>=c>c-1, 所以由抽屉定理，可知必有两个或两个以上个数字对c取余的余数相等，假设有2个数，分别为

A,B， A mod c =B mod c，则（A-B）一定是 c 的整数倍，所以还是有解。


这个题和poj2356非常相似，

代码如下，（因为该题可以一步一步的求sum，而不用sum[]记录每一个的和,所以可以不用数组，只用一个变量即可，看代码吧）


#include <stdio.h>
#include <string.h>
#include <math.h>
typedef __int64 int64;

int64 a[100000],mod[100000];

int main()
{
	int64 i,j,c,n,sum;
	while(scanf("%I64d%I64d",&c,&n) ,c||n)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%I64d",&a[i]);
			mod[i]=-1;
		}
		sum=0;
	//	memset(mod,-1,sizeof(mod));
		for(i=1;i<=n;i++)
		{
			sum+=a[i];
			sum%=c;
			if(sum==0)
			{
				for(j=1;j<i;j++)
					printf("%I64d ",j);
				printf("%I64d\n",i);
				break;
			}
			if(mod[sum]!=-1)
			{
				for(j=mod[sum]+1;j<i;j++)
					printf("%I64d ",j);
				printf("%I64d\n",i);
				break;
			}
			mod[sum]=i;
		}
	}
	return 0;
}


联系
我们