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
#include <stdio.h>
#include <string.h>
int num1,num2,num3,arr[10001],tmp[10001];
int main(){
freopen("in.txt","r",stdin);
while(true){
scanf("%d %d %d", &num1, &num2, &num3);
if(num1 == 0 && num2 == 0 && num3 == 0)
break;
// int l = num1 + num2 * 2 + num3 * 5;
int i,j;
memset(arr,0,sizeof(arr));
memset(tmp,0,sizeof(tmp));
for(i=0; i<=num1; i++){
arr[i] = 1;
tmp[i] = 0;
}
// int m = max(num1, num2 * 2 + num1);
int m = num2 * 2 + num1;
// printf("%d\n",m);
for(i=0; i<=m; i++){
for(j=0; j+i <= m; j += 2){
tmp[j+i] += arr[i];
}
}
for(i=0; i<=m; i++){
arr[i] = tmp[i];
tmp[i] = 0;
}
m += 5*num3;
for(i=0; i<=m; i++){
for(j=0; j+i <= m; j += 5){
tmp[j+i] += arr[i];
}
}
for(i=1; i<=m; i++){
if(tmp[i] == 0)
break;
}
printf("%d\n",i);
}
return 0;
}
分享到:
相关推荐
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码
acm 技术大牛 课件 HDU ...(lecture_06)母函数 (lecture_7)特殊的数 (lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu 1695 GCD(欧拉函数+容斥原理).docx
杭电ACMhdu1163
hdu ACM 各种排序
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
NULL 博文链接:https://128kj.iteye.com/blog/1734821
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU 动态规划(46道题目
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。