357 - Let Me Count The Ways
Moderator: Board moderators
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
357 - Let Me Count The Ways
Hi!
Could anyone give test data with answers...
I have no idea why I get WA
Could anyone give test data with answers...
I have no idea why I get WA

Can someone let me know why this doesn't work? I get WA.
Code: Select all
#include <stdio.h>
void main()
{
long C[100],i,j,k,N;
const long Denominations[]={50,25,10,5,1};
for(i=0;i<100;i++)
C[i]=0;
C[0]=1;
for(i=0;i<5;i++)
{
j=Denominations[i];
for(k=j;k<=99;k++)
{
C[k]+=C[k-j];
}
}
while(scanf("%d",&N)!=EOF)
{
if(C[N]!=1)
printf("There are %d ways to produce %d cents change.n",C[N],N);
else
printf("There is only 1 way to produce %d cents change.n",N);
}
}
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
I use "mail". In the console I just type "mail judge@uva.es < prog.cpp" (that's unix, *of course*)
357WA..
I do'nt know why I always get WA? can someone help me?
[cpp]#include<stdio.h>
#define MAX 101
int way[MAX] = {0};
void Dynamic()
{
int i, j;
int cent[] = { 1, 5, 10, 25, 50 };
for( i = 0 ; i < MAX ; i++ ) way = 1;
for( i = 1 ; i < 5 ; i++ )
for( j = i ; j < MAX ; j++ )
way[j] = way[j] + way[j-cent];
}
void main()
{
int n;
Dynamic();
while( scanf( "%d", &n )==1 ){
if( way[n]==1 )
printf( "There is only 1 way to produce %d cents change.\n", n );
else
printf( "There are %d ways to produce %d cents change.\n", way[n], n );
}
}[/cpp]
[cpp]#include<stdio.h>
#define MAX 101
int way[MAX] = {0};
void Dynamic()
{
int i, j;
int cent[] = { 1, 5, 10, 25, 50 };
for( i = 0 ; i < MAX ; i++ ) way = 1;
for( i = 1 ; i < 5 ; i++ )
for( j = i ; j < MAX ; j++ )
way[j] = way[j] + way[j-cent];
}
void main()
{
int n;
Dynamic();
while( scanf( "%d", &n )==1 ){
if( way[n]==1 )
printf( "There is only 1 way to produce %d cents change.\n", n );
else
printf( "There are %d ways to produce %d cents change.\n", way[n], n );
}
}[/cpp]
-
- New poster
- Posts: 3
- Joined: Fri Jun 28, 2002 11:27 pm
- Location: California
IMO your formulation might be wrong there ... For instance, let's say you do bottom-up process like you described previously, ... you can't really tell if one element of your DP array is 'final' ...
To clarify what I meant, your first loop (i = 1) will compute this:
i = 1, cent = 5
--------------------
ways[5] = ways[5] + ways[0]; --> 2
ways[6] = ways[6] + ways[1]; --> 2
ways[7] = ways[7] + ways[2]; --> 2
ways[8] = ways[8] + ways[3]; --> 2
ways[9] = ways[9] + ways[4]; --> 2
ways[10] = ways[10] + ways[5]; --> 3
ways[11] = ways[11] + ways[6]; --> 3
from ways[5] to ways[9] ... we know that those are already the answer (2 ways) ... but for 10 and 11, we know that those are "not final" yet since later on when (i = 2), you would increment it again ...
But if we continue for (i = 1) loop ... you would later calculate 15 that relies on ways[10] ... and 16 that relies on ways[11] ... Unless you can proof that subsequent calculations will take care of this then I believe you need to adjust your formulations a little bit ...
I'll post my idea shortly after this ...
Good luck ...
To clarify what I meant, your first loop (i = 1) will compute this:
i = 1, cent = 5
--------------------
ways[5] = ways[5] + ways[0]; --> 2
ways[6] = ways[6] + ways[1]; --> 2
ways[7] = ways[7] + ways[2]; --> 2
ways[8] = ways[8] + ways[3]; --> 2
ways[9] = ways[9] + ways[4]; --> 2
ways[10] = ways[10] + ways[5]; --> 3
ways[11] = ways[11] + ways[6]; --> 3
from ways[5] to ways[9] ... we know that those are already the answer (2 ways) ... but for 10 and 11, we know that those are "not final" yet since later on when (i = 2), you would increment it again ...
But if we continue for (i = 1) loop ... you would later calculate 15 that relies on ways[10] ... and 16 that relies on ways[11] ... Unless you can proof that subsequent calculations will take care of this then I believe you need to adjust your formulations a little bit ...
I'll post my idea shortly after this ...
Good luck ...
-
- New poster
- Posts: 3
- Joined: Fri Jun 28, 2002 11:27 pm
- Location: California
My idea of this is using 2D approach instead of 1D array ... the first dimension is obviously the amount of change, and the 2nd dimension is the minimum-coin-index ... To calculate the number of ways, we can define a recursive function, say, getWays():
For instance, to count number of ways we can produce 25 cents change, I'll use getWays(25, 0), where 25 is the target-change, and 0 here means that we can use coin[0], coin[1], and up ...:
getWays(amount=25, minIdx=0):
// if amount < 0 --> return 0
// if amount == 0 --> return 1
// if known(amount, minIdx) --> return data[amount][minIdx]
w = 0
i=minIdx=0, coin=1 as the starting point ... w += getWays(25-1, 0)
i=1, coin=5 as the starting point ... w += getWays(25-5, 1)
i=2, coin=10 as the starting point ... w += getWays(25-10, 2)
i=3, coin=25 as the starting point ... w += getWays(25-25, 3)
i=4, coin=50 as the starting point ... w += getWays(25-50, 4)
The idea behind minimum-coin-index is to prevent this kind of sequence to occur:
1 + 1 + 5 + 1 ...
Because it's been taken care by sequence:
1 + 1 + 1 + 5 ... which is in increasing order ...
I hope you got the idea, this is my first post, so I might be confusing everybody
...
After this it's only a matter of putting the code together and hope it will work ...
Best regards,
-LG-
For instance, to count number of ways we can produce 25 cents change, I'll use getWays(25, 0), where 25 is the target-change, and 0 here means that we can use coin[0], coin[1], and up ...:
getWays(amount=25, minIdx=0):
// if amount < 0 --> return 0
// if amount == 0 --> return 1
// if known(amount, minIdx) --> return data[amount][minIdx]
w = 0
i=minIdx=0, coin=1 as the starting point ... w += getWays(25-1, 0)
i=1, coin=5 as the starting point ... w += getWays(25-5, 1)
i=2, coin=10 as the starting point ... w += getWays(25-10, 2)
i=3, coin=25 as the starting point ... w += getWays(25-25, 3)
i=4, coin=50 as the starting point ... w += getWays(25-50, 4)
The idea behind minimum-coin-index is to prevent this kind of sequence to occur:
1 + 1 + 5 + 1 ...
Because it's been taken care by sequence:
1 + 1 + 1 + 5 ... which is in increasing order ...
I hope you got the idea, this is my first post, so I might be confusing everybody

After this it's only a matter of putting the code together and hope it will work ...

Best regards,
-LG-
HELP
I am very sure that there is nothing wrong with my code.
But I get WA....
[cpp]// ACM Problem 357
// Let Me Count The Ways
// Done by Teh Ming Han
#include <stdio.h>
// 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent
int main(){
const int money[5]={50,25,10,5,1};
int value,i,j;
unsigned long ways[99]={0};
ways[0] = 1;
for (i=0;i<5;i++)
for (j = money;j<=99;j++)
ways[j] += ways[j - money];
while (scanf("%d",&value)==1){
if (ways[value]==1) printf("There is only 1 way to produce %d cents change.\n",value);
else printf("There are %d ways to produce %d cents change.\n",ways[value],value);
}
return 0;
}[/cpp]
Can someone PLEASE help??
But I get WA....
[cpp]// ACM Problem 357
// Let Me Count The Ways
// Done by Teh Ming Han
#include <stdio.h>
// 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent
int main(){
const int money[5]={50,25,10,5,1};
int value,i,j;
unsigned long ways[99]={0};
ways[0] = 1;
for (i=0;i<5;i++)
for (j = money;j<=99;j++)
ways[j] += ways[j - money];
while (scanf("%d",&value)==1){
if (ways[value]==1) printf("There is only 1 way to produce %d cents change.\n",value);
else printf("There are %d ways to produce %d cents change.\n",ways[value],value);
}
return 0;
}[/cpp]
Can someone PLEASE help??
:: HanWorks ::