Posted:

**Thu Jan 24, 2002 6:56 pm**what is the output if testcase is "0" ?

Page **1** of **7**

Posted: **Thu Jan 24, 2002 6:56 pm**

what is the output if testcase is "0" ?

Posted: **Thu Jan 24, 2002 8:18 pm**

There is only 1 way to produce 0 cents change.

Posted: **Fri Mar 01, 2002 12:18 pm**

Hi!

Could anyone give test data with answers...

I have no idea why I get WA

Could anyone give test data with answers...

I have no idea why I get WA

Posted: **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);
}
}
```

Posted: **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?

Posted: **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.

Posted: **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*)

Posted: **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.

Posted: **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]

[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

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]

Posted: **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++ )*

I guess it should be like this

for( j = cent

Posted: **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?

[cpp] for( i = 1 ; i < 5 ; i++ )

for( j = cent

way[j] = way[j] + way[j-cent

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

Posted: **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 ...

To clarify what I meant, your first loop (i = 1) will compute this:

i = 1, cent

--------------------

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

Posted: **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-

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

i=1, coin

i=2, coin

i=3, coin

i=4, coin

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-

Posted: **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??

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

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

Posted: **Thu Feb 06, 2003 6:01 pm**

This code is almost correct.

But try "99"

I think the answer is 252.

But try "99"

I think the answer is 252.