674 - Coin Change

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

Moderator: Board moderators

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 674 - Coin Change

Post by Shahidul.CSE » Tue Jan 13, 2015 6:50 am

brianfry713 wrote:Do you need to reset preCal at every test case?
Yes, I myself also thought that I don't need to reset preCal at every test case. And when I tried without reset preCal at every test case, it gave wrong outputs. So then, when reset preCal at every test case, it gives correct outputs, but got TLE.

For example, if I don't reset preCal at every test case, for the input bellow it gives the same output for every test case:

Code: Select all

    0
    57
    129
    134
    239
    277
    300
    386
    393
    455
    510
    535
    568
    610
    637
    642
    790
    1426
    1446
    1498
    1503
    1590
    1600
    1624
    1635
    1647
    1691
    1722
    1931
    2116
    2261
    2455
    2547
    2663
    2703
    2707
    2765
    2827
    2915
    3258
    3349
    3915
    3960
    4261
    4691
    4800
    4862
    4928
    5001
    5151
    5246
    5331
    5376
    5559
    5826
    5853
    5975
    6071
    6168
    6239
    6321
    6423
    6482
    6543
    6620
    6796
    6962
    6973
    7026
    7104
    7355
    7414
    7481
    7489
program gave output

Code: Select all

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
But when reset preCal at every case, it gives correct outputs.
So, what to do?
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 674 - Coin Change

Post by brianfry713 » Tue Jan 13, 2015 10:42 pm

Rewrite your code.
Precompute the results for all possible inputs.
http://www.geeksforgeeks.org/dynamic-pr ... in-change/
Check input and AC output for thousands of problems on uDebug!

messiNayan
New poster
Posts: 7
Joined: Thu Feb 20, 2014 7:07 pm

Re: 674 - Coin Change

Post by messiNayan » Fri Jul 10, 2015 3:21 pm

Getting Wrong answer:Help me
#include<stdio.h>
#include<string.h>


int coins[] = { 50, 25, 10, 5, 1 };
int dp[6][7490];
int makeAmount(int i, int amount);
int main(void)
{
int amount;
memset(dp, -1, sizeof(dp)); //
while(1)// (scanf("%d", &amount) != EOF)
{
scanf("%d", &amount);
printf("%d\n", makeAmount(0, amount));
}

return 0;
}

int makeAmount(int i, int amount)
{
if (dp[amount] != -1)
return dp[amount];

int ret1 = 0, ret2 = 0;

if (i >= 5)
{
if (amount == 0)
return 1;
else
return 0;
}

if (amount - coins >= 0)
ret1 = makeAmount(i, (amount - coins));
ret2 = makeAmount((i + 1), amount);
return (dp[amount] = (ret1 + ret2));
}

Post Reply

Return to “Volume 6 (600-699)”