Holding Bin-Laden Captive!
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8814Accepted Submission(s): 3963
Problem Description
We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!
“Oh, God! How terrible! ”
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!
Input
Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.
Output
Output the minimum positive value that one cannot pay with given coins, one line for one case.
Sample Input
Sample Output
4
题意:
用125的硬币买不到的东西的价值(输出最小的)3者数量分别为num1num2num3
#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);
}
}
分享到:
相关推荐
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码
hdu ACM代码 每种算法都有分类 大三了,没有时间弄ACM,这些要删了
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
acm 技术大牛 课件 HDU ...(lecture_06)母函数 (lecture_7)特殊的数 (lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
hdu 1695 GCD(欧拉函数+容斥原理).docx
杭电ACMhdu1163
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
hdu2101AC代码
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
ACM HDU题目分类,我自己总结的大概只有十来个吧