## 357 - Let Me Count The Ways

Moderator: Board moderators

seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am
what is the output if testcase is "0" ?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
There is only 1 way to produce 0 cents change.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### 357 - Let Me Count The Ways

Hi!

Could anyone give test data with answers...

I have no idea why I get WA

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
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);
}
}
``````

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
James: No idea what you're doing. I just got your program accepted. Maybe you submit it with the wrong number?

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Stefan, what mail program do you use to submit? I normally use hotmail and that works well. Last night, I was using Outlook and I think that was screwing with my code. Thanks for your help. Sorry to have bothered you.

Stefan Pochmann
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*)

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
I guess sometimes simplicity is best. I think I might switch to coding on my Debian box since Visual C++ is soooo loose on bounds checking and such.

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

### 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]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
for( j = i ; j < MAX ; j++ )

I guess it should be like this

for( j = cent ; j < MAX ; j++ )

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

### change

I try to change the loop, it becomes

[cpp] for( i = 1 ; i < 5 ; i++ )
for( j = cent ; j < MAX ; j++ )
way[j] = way[j] + way[j-cent];[/cpp]

but I still get a WA..., is it has other bug?

easton2048
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 ...

easton2048
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-

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

### 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]