uva 357 - Let Me Count The Ways
Let Me Count The Ways
After making a purchase at a large department store, Mel's change was 17 cents. He received 1 dime, 1 nickel, and 2 pennies. Later that day, he was shopping at a convenience store. Again his change was 17 cents. This time he received 2 nickels and 7 pennies. He began to wonder ' "How many stores can I shop in and receive 17 cents change in a different configuration of coins? After a suitable mental struggle, he decided the answer was 6. He then challenged you to consider the general problem.
Write a program which will determine the number of different combinations of US coins (penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c) which may be used to produce a given amount of money.
Input
The input will consist of a set of numbers between 0 and 30000 inclusive, one per line in the input file.
Output
The output will consist of the appropriate statement from the selection below on a single line in the output file for each input value. The number m is the number your program computes, n is the input value.
There are m ways to produce n cents change.
There is only 1 way to produce n cents change.
Sample input
17
11
4
Sample output
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.
, , ;
b[I]; a[I][J]=a[I][J-1]+a[I-b[I]][J];
0 1 2 3 4 5 6 7 8 9 10 15 20 25
0
1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 2 2 2 2 2 3 4 5 6
10
25
50
#include<stdio.h>
#include<string.h>
#define max 30000
long long i,j,n,a[max+1][6],b[6]={0,1,5,10,25,50};
int main()
{
memset(a,0,sizeof(a));
for (i=1;i<6;i++)
{
++a[b[i]][i-1];// b[I];
for (j=1;j<=max;j++)
{
if (j-b[i]>=0) a[j][i]=a[j][i-1]+a[j-b[i]][i];
else a[j][i]=a[j][i-1];
}
}
while (scanf("%lld",&n)!=EOF)
if (a[n][5]==1||n==0) printf("There is only 1 way to produce %lld cents change.
",n);// 0 1 Y-Y
else printf("There are %lld ways to produce %lld cents change.
",a[n][5],n);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java에서 InputStream, String, File 간의 상호 전환 비교
InputStream, String, File 상호 전환
1. String --> InputStream
2. InputStream --> String 오늘 인터넷에서 또 다른 방법을 보았는데, 특별히 가지고 와서 공...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
17
11
4
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.
, , ;
b[I]; a[I][J]=a[I][J-1]+a[I-b[I]][J];
0 1 2 3 4 5 6 7 8 9 10 15 20 25
0
1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 2 2 2 2 2 3 4 5 6
10
25
50
#include<stdio.h>
#include<string.h>
#define max 30000
long long i,j,n,a[max+1][6],b[6]={0,1,5,10,25,50};
int main()
{
memset(a,0,sizeof(a));
for (i=1;i<6;i++)
{
++a[b[i]][i-1];// b[I];
for (j=1;j<=max;j++)
{
if (j-b[i]>=0) a[j][i]=a[j][i-1]+a[j-b[i]][i];
else a[j][i]=a[j][i-1];
}
}
while (scanf("%lld",&n)!=EOF)
if (a[n][5]==1||n==0) printf("There is only 1 way to produce %lld cents change.
",n);// 0 1 Y-Y
else printf("There are %lld ways to produce %lld cents change.
",a[n][5],n);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java에서 InputStream, String, File 간의 상호 전환 비교InputStream, String, File 상호 전환 1. String --> InputStream 2. InputStream --> String 오늘 인터넷에서 또 다른 방법을 보았는데, 특별히 가지고 와서 공...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.