学步园

Run ID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
7537109	kingpro	1014	Accepted	164K	0MS	C++	702B	2010-08-26 18:12:16

 

#include <stdio.h>
bool Check(int * val)
{
	int half=val[0]/2;
	for(int j1=0; j1<=val[1]; j1++) for(int j2=0; j2<=val[2]; j2++) for(int j3=0; j3<=val[3]; j3++) for(int j4=0; j4<=val[4]; j4++) for(int j5=0; j5<=val[5]; j5++) for(int j6=0; j6<=val[6]; j6++)
		if(j1*1+j2*2+j3*3+j4*4+j5*5+j6*6==half) return true;
	return false;
}
int main()
{
	for(int n=1; ; n++)
	{
		int val[7]={0}; bool isEnd=true;
		for(int i=1; i<=6 && (scanf("%d", &val[i]), isEnd && (isEnd=!val[i]), val[i]>6 && (val[i]=6-val[i]%2), val[0]+=i*val[i], true); i++);
		if(isEnd) break;
		printf("Collection #%d:\n%s\n\n", n, (val[0]%2!=0 || !Check(val)) ? "Can't be divided." : "Can be divided.");
	}
	return 0;
}

 

大致的意思是，一堆石头，表示1-6的值，判断能否分平均分两堆。很明显，如果石头k有n个且可分，那么k变成n+2个也可分。反过来却不一定，但是，反过来时却不一定成立，然而，当n>6时，成立。就是说，石头k有n(n>6)个 与石头k有(6-n%2)个的情况的结果是一样的。

严格的数学证明还没有表示出来，思路是这样的：

如果可分，则左右两边拿去相同值的相同个数的石头，那么，剩下的两堆石头的值仍然相等，如果尽可能的拿走石子，剩下的石子中，假设左边值为k的石子数量为0，右边数量为k的石子的数量为m。此时，在左边一堆中，必定有若干个石子的值的和与前面所提的m个k中的若干个的值的和相同，也可以消去。再此时，能保证等值条件成立的m的最小值，可以猜到是5或6(m的奇偶性判断)。

如此，值为k的m个石子与(6-m%2)个石子是等价的，若可分，则可分，若不可分，则亦不可分。

具体证明过程，我再想想。