## 357 - Let Me Count The Ways

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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
Location: Pasadena, CA
Can someone let me know why this doesn't work? I get WA.

Code: Select all

``````#include <stdio.h>

void main()
{
long C,i,j,k,N;

const long Denominations[]={50,25,10,5,1};

for(i=0;i<100;i++)
C[i]=0;
C=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
Location: Pasadena, CA
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
Location: Pasadena, CA
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 = ways + ways; --> 2
ways = ways + ways; --> 2
ways = ways + ways; --> 2
ways = ways + ways; --> 2
ways = ways + ways; --> 2
ways = ways + ways; --> 3
ways = ways + ways; --> 3

from ways to ways ... 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 ... and 16 that relies on ways ... 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, coin, 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={50,25,10,5,1};
int value,i,j;

unsigned long ways={0};
ways = 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 ::
supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:
This code is almost correct.
But try "99" I think the answer is 252.