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[kj];
}
}
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[jcent];
}
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[jcent];
}
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 bottomup 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 minimumcoinindex ... 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 targetchange, 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(251, 0)
i=1, coin=5 as the starting point ... w += getWays(255, 1)
i=2, coin=10 as the starting point ... w += getWays(2510, 2)
i=3, coin=25 as the starting point ... w += getWays(2525, 3)
i=4, coin=50 as the starting point ... w += getWays(2550, 4)
The idea behind minimumcoinindex 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 targetchange, 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(251, 0)
i=1, coin=5 as the starting point ... w += getWays(255, 1)
i=2, coin=10 as the starting point ... w += getWays(2510, 2)
i=3, coin=25 as the starting point ... w += getWays(2525, 3)
i=4, coin=50 as the starting point ... w += getWays(2550, 4)
The idea behind minimumcoinindex 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>
// 50cent, 25cent, 10cent, 5cent, and 1cent
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>
// 50cent, 25cent, 10cent, 5cent, and 1cent
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 ::