Holding Bin-Laden Captive!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24475 Accepted Submission(s): 10894
“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 (Coin) (Three Kinds– 1, 2, 5), and their Number is Num_1, NUM_2 and NUM_5 Respectively, please output the minimum value that you cannound party
You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!
Mother function, find out:portal teleport door 2These two blogs can be understood, especially the first. This question can be used as a parent function template
/*This is a combination of a limited number of numbers. If each banknote has unlimited Zhang, then there will be a range of inquiries
The maximum value of this range is the maximum value MAX, that is, max = n; then it will be changed to j <= n; j+k <= n.
*/
#include <cstdio>
#include <cstring>
TypeDef long long ll;
const int n = 1000 * (1+2+5)+5;
// At most 1,000, the array to be opened is the possible maximum money number
int Cost [3] = {1, 2, 5}; // Three face value banknotes
Ll c1 [n], c2 [n];
// C2 is a polynomial of temporary merging, which is cleared at each time; C1 is the final merger polynomial, and the number of schemes for each combination is preserved
int Num [3];
int Max;
int Main ()
{{
While (~ Scanf ("%D%D%D", & NUM [0], & NUM [1], & Num [2]))
{// How many money each face value is
if (num [0] == 0 && num [1] == 0 && num [2] == 0) break;
MEMSET (C1, 0, SIZEOF (C1)); // Initialize
MEMSET (C2, 0, SIZEOF (C2));
Max = num [0] + num [1] * 2 + num [2] * 5; // Calculate the maximum value of this money. Border
c1 [0] = 1; // The situation of 0 at the beginning is a kind
for (int i = 0; i <3; i ++)
{// three kinds of banknotes
for (int j = 0; j <= num [i] * Cost [i]; j += Cost [i])
{// Cost of banks with face value, COST [i]
for (int k = 0; J +k <= max; k ++)
{{
c2 [j + k] + = c1 [k];
}
}
for (int j = 0; j <n; j ++)
{// copy the data of C2 to C1 and empty C2
c1 [j] = c2 [j];
c2 [j] = 0;
}
}
for (int i = 1; i <= max +1; i ++)
{{
if (! C1 [i])
{// zero, it means that it is impossible
Printf ("%d \ n", i);
Break;
}
}
}
}