OJ Board

what is the output if testcase is "0" ?

There is only 1 way to produce 0 cents change.

Hi!

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.

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

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.

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

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.

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++ )

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?

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

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-

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

This code is almost correct.
But try "99"

I think the answer is 252.