Holding Bin-Laden Captive!Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8814 Accepted Submission(s): 3963
Problem Description
Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up! Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem? “Given some Chinese Coins (硬币) (three kinds-- 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.” You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush! InputOutputSample InputSample Output#include "stdio.h"int c1[10000],c2[10000];int main(){ int i,j,k,num1,num2,num3,n; while(scanf("%d %d %d",&num1,&num2,&num3)!=EOF) { if(!num1&&!num2&&!num3) break; n=num3*5+num2*2+num1; for(i=0;i<=n;i++) { c1[i]=0; c2[i]=0; } for (i=0;i<=num1;i++) c1[i]=1; for(j=0;j<=num1;j++) // for (k=0;k+j<=num2*2;k=k+2)//num2*2表示最多可能达到的次数 for (k=0;k<=num2*2;k=k+2)//num2*2表示最多可能达到的次数 { //注意 这里不要用k+j<=num2 因为以前求整数拆分输入数n 要保证次数小于n 因为最大为 //x的n次方 表示为1个重为n的砝码 这里是求多项式相乘 不用限制了 c2[j+k]+=c1[j]; } for (j=0;j<=num2*2+num1;j++)//因为 下面的c2[j] 中的下标最大为j+k 由上一步可以看出 而j最大为num1 k最大为num2*2 { c1[j]=c2[j]; c2[j]=0; } for(j=0;j<=num2*2+num1;j++)//num1和num2*2不一定那个大那 要表示出所有的项数 所以要这样 for(k=0;k<=num3*5;k+=5) c2[j+k]+=c1[j]; for (j=0;j<=num3*5+num2*2+num1;j++) { c1[j]=c2[j]; c2[j]=0; } for (i=0;i<=n;i++) if(!c1[i]) {printf("%d\n",i);break;} if(i==n+1) printf("%d\n",i); }}