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

Post Reply
seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am

Post by seolv » Thu Jan 24, 2002 6:56 pm

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

Post by Ivan Golubev » Thu Jan 24, 2002 8:18 pm

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

Post by cyfra » Fri Mar 01, 2002 12:18 pm

Hi!

Could anyone give test data with answers...

I have no idea why I get WA :sad:

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 06, 2002 3:23 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:

Post by Stefan Pochmann » Wed Mar 06, 2002 5:01 am

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

Post by C8H10N4O2 » Wed Mar 06, 2002 1:34 pm

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:

Post by Stefan Pochmann » Wed Mar 06, 2002 10:41 pm

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

Post by C8H10N4O2 » Thu Mar 07, 2002 12:02 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..

Post by T.T. » Thu Jul 25, 2002 8:02 am

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

Post by .. » Thu Jul 25, 2002 9:44 am

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

Post by T.T. » Thu Jul 25, 2002 10:02 am

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

Post by easton2048 » Sat Jul 27, 2002 9:00 am

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

Post by easton2048 » Sat Jul 27, 2002 9:26 am

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-

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

HELP

Post by Ming Han » Sun Nov 17, 2002 5:28 pm

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??
:: HanWorks ::

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by supermin » Thu Feb 06, 2003 6:01 pm

This code is almost correct.
But try "99" :)

I think the answer is 252.

Post Reply

Return to “Volume 3 (300-399)”