357 - Let Me Count The Ways

[seolv]

what is the output if testcase is "0" ?

[Ivan Golubev]

There is only 1 way to produce 0 cents change.

[cyfra]

Hi!

Could anyone give test data with answers...

I have no idea why I get WA

[C8H10N4O2]

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]

James: No idea what you're doing. I just got your program accepted. Maybe you submit it with the wrong number?

[C8H10N4O2]

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]

I use "mail". In the console I just type "mail judge@uva.es < prog.cpp" (that's unix, *of course*)

[C8H10N4O2]

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

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]

[..]

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

I guess it should be like this

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

[T.T.]

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]

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]

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]

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

[supermin]

This code is almost correct.
But try "99"

I think the answer is 252.