Holding Bin-Laden Captive!
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
1 1 3
0 0 0
Sample Output
4
Author
lcy
题目类型：普通母函数
算法分析：这是一种步长特定且每一个多项式的长度不同的问题，直接使用普通母函数求解即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 10000 + 7; const int maxn = 10000 + 66;//注意maxn要大于多项式指数的最高值 const int step[] = {6666, 1, 2, 5};//每个表达式的步长 //coeff数组存储每一指数值下的系数值，temp数组存储当前两个多项式相乘的系数值，ans数组存储各个多项式的个数 long long coeff[maxn], temp[maxn], ans[maxn]; void Init () { memset (coeff, 0, sizeof (coeff)); memset (temp, 0, sizeof (temp)); } //在调用GenerFunction之前一定先调用Init函数 void GenerFunction (long long expnum, long long upp)//所有数组的下标从1开始 { for (long long i = 0; i <= ans[1] * step[1]; i += step[1]) //初始化第一个多项式的系数值 coeff[i] = 1; for (long long i = 2; i <= expnum; i++) { for (long long j = 0; j <= upp; j++) { for (long long k = 0; j + k <= upp && k <= ans[i] * step[i]; k += step[i]) temp[k+j] += coeff[j];//x ^ k * x ^ j = x ^ (k + j)的系数值 } for (long long j = 0; j <= upp; j++) { coeff[j] = temp[j]; temp[j] = 0; } } } int main() { // ifstream cin ("aaa.txt"); while (cin >> ans[1] >> ans[2] >> ans[3]) { if (ans[1] == 0 && ans[2] == 0 && ans[3] == 0) break; Init (); int len = 1 * ans[1] + 2 * ans[2] + 5 * ans[3]; GenerFunction (3, len); int i; for (i = 1; i <= len; i++) if (coeff[i] == 0) break; cout << i << endl; } return 0; } |
- « 上一篇：hdu1075
- hdu1087：下一篇 »