Ignatius and the Princess III
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 23902 Accepted Submission(s): 16627
Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input
4
10
20
Sample Output
5
42
627
Author
Ignatius.L
Recommend
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <string.h> 5 #include <cstring> 6 #include <math.h> 7 #include <stdio.h> 8 9 #define mem(a) memset(a,0,sizeof(a)) 10 #define maxn 150 11 #define ll long long 12 using namespace std; 13 int a[maxn],b[maxn]; 14 15 int main(){ 16 ios::sync_with_stdio(0); 17 int n; 18 while(scanf("%d",&n)!=EOF){ 19 for(int i=0;i<=n;i++){ 20 a[i]=1; 21 b[i]=0; 22 } 23 24 for(int i=2;i<=n;i++){ 25 for(int j=0;j<=n;j++) 26 for(int k=0;k+j<=n;k+=i) 27 b[k+j]+=a[j]; 28 for(int i=0;i<=n;i++){ 29 a[i]=b[i]; 30 b[i]=0; 31 } 32 } 33 printf("%d ",a[n]); 34 } 35 return 0; 36 }
Square Coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13374 Accepted Submission(s): 9194
Problem Description
People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
Input
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.
Output
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.
Sample Input
2
10
30
0
Sample Output
1
4
27
Source
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <string.h> 5 #include <cstring> 6 #include <math.h> 7 #include <stdio.h> 8 9 #define mem(a) memset(a,0,sizeof(a)) 10 #define maxn 350 11 #define ll long long 12 using namespace std; 13 //int money[]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289}; 14 int a[maxn],b[maxn]; 15 16 int main(){ 17 ios::sync_with_stdio(0); 18 int n; 19 while(scanf("%d",&n)&&n){ 20 for(int i=0;i<=n;i++){ 21 a[i]=1; 22 b[i]=0; 23 } 24 for(int i=2;i*i<=n;i++){ 25 for(int j=0;j<=n;j++) 26 for(int k=0;k+j<=n;k+=i*i) 27 b[k+j]+=a[j]; 28 29 for(int i=0;i<=n;i++){ 30 a[i]=b[i]; 31 b[i]=0; 32 } 33 } 34 printf("%d ",a[n]); 35 } 36 return 0; 37 }
Holding Bin-Laden Captive!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 24244 Accepted Submission(s): 10777
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!
“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 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <string.h> 5 #include <cstring> 6 #include <math.h> 7 #include <stdio.h> 8 #include <cstdio> 9 10 #define mem(a) memset(a,0,sizeof(a)) 11 #define maxn 8010 12 #define BASE 10000 13 #define ll long long 14 15 using namespace std; 16 /* 17 int a[20]; 18 sort(a, a+20, [](int a, int b){return a > b;}) 19 */ 20 21 int a[maxn],b[maxn]; 22 int num[5]; 23 24 int main(){ 25 ios::sync_with_stdio(0); 26 while(scanf("%d%d%d",&num[0],&num[1],&num[2])){ 27 if(num[0]==0&&num[1]==0&&num[2]==0) return 0; 28 int maxx=num[0]*1+num[1]*2+num[2]*5; 29 for(int i=0;i<=maxx;i++){ 30 a[i]=1; 31 b[i]=0; 32 } 33 for(int i=0;i<=num[0];++i) 34 a[i]=1; 35 for(int i=0;i<=num[0];++i) 36 for(int j=0;j<=num[1]*2;j+=2) 37 b[j+i]+=a[i]; 38 for(int i=0;i<=num[1]*2+num[0]*1;i++){ 39 a[i]=b[i]; 40 b[i]=0; 41 } 42 for(int i=0;i<=num[0]*1+num[1]*2;i++) 43 for(int j=0;j<=num[2]*5;j+=5) 44 b[j+i]+=a[i]; 45 for(int i=0;i<=maxx;i++){ 46 a[i]=b[i]; 47 b[i]=0; 48 } 49 int i; 50 for(i=0;i<=maxx;i++){ 51 if(a[i]==0){ 52 printf("%d ",i); 53 break; 54 } 55 } 56 if(i==maxx+1) 57 printf("%d ",i); 58 } 59 return 0; 60 }