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)个石子是等价的,若可分,则可分,若不可分,则亦不可分。
具体证明过程,我再想想。