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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 674 - Coin Change

Post by mf » Fri Dec 19, 2008 10:17 pm

Here's my diff:

Code: Select all

--- Main.java	2008-12-19 23:11:39.000000000 +0300
+++ Main2.java	2008-12-19 23:11:33.000000000 +0300
@@ -5,13 +5,14 @@
 public static void main(String[] args) throws IOException
 {
 BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
+int[] tab = coinchange();
 while(true)
 {
 int n = Integer.parseInt(vhod.readLine());
-System.out.println(coinchange(n));
+System.out.println(tab[n]);
 }
 }
-public static int coinchange(int n)
+public static int[] coinchange()
 {
 int tab[]=new int[7490];
 int coin[] = new int[5];
@@ -33,6 +34,6 @@
 tab[j] += tab[j-c];
 }
 }
-return tab[n];
+return tab;
 }
 }
(note - it's for your unindented version as you posted above, you should've really used

Code: Select all

 [ /code] tags next time)

mimi
New poster
Posts: 5
Joined: Fri Dec 19, 2008 6:39 pm

Runtime error

Post by mimi » Fri Dec 19, 2008 11:20 pm

I change it.But now it says Runtime error?? :oops:

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 674 - Coin Change

Post by mf » Fri Dec 19, 2008 11:34 pm

Oh... it's because your program doesn't have any normal way of termination. All you have is an infinite while(true) loop which aborts only due to a NumberFormatException being thrown out of parseInt at the end of input, when readLine returns null. And that exception is then reported back to you as a 'Runtime Error' verdict by the judge.

Sorry that I didn't notice it earlier, it didn't even occur to me that someone could make such a mistake...

What you have to do is check whether readLine() returned null, (it happens when there's no more input), and if so, stop the while loop and exit.

mimi
New poster
Posts: 5
Joined: Fri Dec 19, 2008 6:39 pm

Re: 674 - Coin Change

Post by mimi » Sat Dec 20, 2008 12:18 am

-What you have to do is check whether readLine() returned null, (it happens when there's no more input), and if so, stop the while loop and exit
Can you please write (code in java)how to do it? :oops:

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 674 - Coin Change

Post by mf » Sat Dec 20, 2008 12:34 am

Code: Select all

--- Main2.java	2008-12-19 23:11:33.000000000 +0300
+++ Main3.java	2008-12-20 01:33:20.000000000 +0300
@@ -8,7 +8,9 @@
 int[] tab = coinchange();
 while(true)
 {
-int n = Integer.parseInt(vhod.readLine());
+String s = vhod.readLine();
+if (s == null) break;
+int n = Integer.parseInt(s);
 System.out.println(tab[n]);
 }
 }

mimi
New poster
Posts: 5
Joined: Fri Dec 19, 2008 6:39 pm

Re: 674 - Coin Change

Post by mimi » Sat Dec 20, 2008 12:44 am

Thank you mf!!! :D My code is accepted now.

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

674 - Coin Change

Post by sazzadcsedu » Thu Jan 29, 2009 10:27 pm

why TLE??
my code

Code: Select all

 #include <stdio.h>
                     #include<math.h>

                   #define MAXTOTAL 30000
  
                   
                     //const double eps = 1e-7;

                    long nway[MAXTOTAL+1];
                    int coin[5] = { 50,25,10,5,1};

                   int main()
				   {

                  
                    int i,j,n,v,c;
				



					
                      while(scanf("%d",&n)==1)

					  {


				

					for(i=0;i<MAXTOTAL;i++)
					{ 
						nway[i]=0;

					}
					
				
 
					 
					    
					// printf("%d\n",n);

                     v = 5;
                     nway[0] = 1; 
                     for (i=0; i<v; i++) 
					 {
                         c = coin[i];
                          for (j=c; j<=n; j++)
                         nway[j] += nway[j-c];
					 }
                       printf("%llu\n",nway[n]);

					}
                         return 0;
				   }
any help /suggestion???
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 674 - Coin Change

Post by newkid » Fri Jan 30, 2009 9:34 pm

@sazzadcsedu
1. nway is declared long but in printf u r using llu (as long long)
2. why do you need to compute the result for each n? you can precompute the result for all possible n.
3. you dont need to set the limit so high. the problem statement says at most 7489..
4. and again please fix your indentation..
hmm..

KRUNCH
New poster
Posts: 8
Joined: Sun May 18, 2008 1:03 pm

Re: 674 - Coin Change

Post by KRUNCH » Thu Apr 01, 2010 10:43 am

Can anybody help me with this one , I tested it on numerous testcases , it works but for no reason it fails on some.

Here's the code

Code: Select all

#include <iostream>

using namespace std;

int main()
{
    int coins[]={1,5,10,25,50};
    int all[10000],n;
    for(int i=0;i<10000;i++)all[i]=0;
    all[0]=1;
    all[1]=1;
    for(int i=0;i<5;i++)
    {
            for(int j=1;j<8000;j++)
            {
                    all[j+coins[i]]+=all[j];
            }
    }
    while(scanf("%d",&n)==1)
    {
            printf("%d\n",all[n]);
    }
}
The input:

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
My output: // note that only the bolded output is wrong

Code: Select all

1
62
558
628
4160
7098
[b]9044[/b]
23124
24216
[b]40570[/b]
[b]61787
73788[/b]
93418
120380
144144
148421
319464
3131855
3305565
3771460
3820626
4732112
4849152
5151289
5276018
5467319
6072570
6503070
10190440
14574076
18894799
25930850
30107714
35816715
37980910
38258165
41409284
45379809
50994880
79289342
88293002
163511040
171076240
229494139
335794790
366569984
386652189
407548350
432699251
486474872
523030235
557449884
576345348
656770352
792830259
806417782
874084640
933653312
993015250
1038534000
1095890112
1166373065
1210262495
1255379026
1313534866
1461345024
1607484130
1616679680
1667962743
1739848682
1996345212
2061906700
2140421225
2146113925
The expected output according to a post on the first page:

Code: Select all

1
62
558
628
4160
7098
9590
23124
24216
42230
64064
76384
93418
124124
144144
148421
327216
3131855
3305565
3771460
3820626
4790368
4908497
5151289
5339224
5467319
6072570
6503070
10190440
14574076
18894799
26139150
30107714
35816715
37980910
38258165
41705076
45379809
51340620
79289342
88293002
164338960
171932760
229494139
335794790
368086385
386652189
407548350
432699251
486474872
523030235
557449884
576345348
656770352
792830259
806417782
876993480
933653312
993015250
1038534000
1095890112
1166373065
1210262495
1255379026
1317482439
1461345024
1607484130
1616679680
1667962743
1739848682
2001748100
2061906700
2140421225
2146113925

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 674 - Coin Change

Post by helloneo » Thu Apr 01, 2010 10:36 pm

There is a simple test case your code doesn't pass..

input:
5

output should be
2

You can try to reason out..

KRUNCH
New poster
Posts: 8
Joined: Sun May 18, 2008 1:03 pm

Re: 674 - Coin Change

Post by KRUNCH » Fri Apr 02, 2010 9:35 am

helloneo wrote:There is a simple test case your code doesn't pass..

input:
5

output should be
2

You can try to reason out..
OMG , Thanks dude , I made one of the stupidest mistakes ever -.-'

viharvera
New poster
Posts: 1
Joined: Fri Dec 10, 2010 12:28 pm

Re: 674 - Coin Change

Post by viharvera » Fri Dec 10, 2010 1:02 pm

Hi!

I`m new to uva, so sorry for the newbie question. I have the following code:

Code: Select all

#include<iostream>

using namespace std;
int main(int argc, char* argv[])
{
	cout.setf(ios::fixed);
	cout.precision(3);
	int coins[]={1,5,10,25,50};
	long dp[5][7594]={{0}};	
	for(int c=0;c<5;++c){
		dp[c][0]=1;
		for(int i=1;i<7494;++i){
			if(i-coins[c]>-1)
				dp[c][i]+=dp[c][i-coins[c]];
			if(c>0)
				dp[c][i]+=dp[c-1][i];
		}
	}
	int i;
	cin>>i;
	cout<<dp[4][i];
	while(!cin.eof()){
		cin>>i;
		cout << endl << dp[4][i];
	}
	return 0;
}
It is like this, because i tried to avoid any minor mistake, but apparently it is still not good, because i get a Wrong Answer for it. I checked for all the sample input/output that i have found here, and i got the correct answer for it, so i`m thinking its something else. Any advice?

fsafs168
New poster
Posts: 1
Joined: Fri May 25, 2012 7:21 pm

Re: 674 - Coin Change

Post by fsafs168 » Fri May 25, 2012 7:29 pm

Accepted????Why?

this is my code:

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[10000]={1,1};
int b[5]={1,5,10,25,50};
int main()
{
    int i,j;
    for(i=0;i<5;i++)
    {
        for(j=2;j<10000;j++)
        {
            if(j>=b[i])
                a[j]+=a[j-b[i]];
        }
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            printf("0\n");
        printf("%d\n",a[n]);
    }
    return 0;
}
I just consider input data:
5
output
2

so,change code a[0]=1 , if n==0 prit 0 and for loop is >=, this is accepted!!!!!!!!! why??????

and i dont konw why a[n]=a[n-50]+a[n-25]+a[n-10]+a[n-5]+a[n-1];
anyone can help me? thns

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 » Sat Jan 10, 2015 7:05 pm

I am getting TLE on UVa 674 – Coin Change, with my bellow code:

Code: Select all

#include <stdio.h>
int availableCents[]={50, 25, 10, 5, 1}, amount, preCal[5][7490];
int change(int pos, int sum)
{
    if(pos==5)
    {
        if(sum==amount)
            return 1;
        else return 0;
    }
    if(preCal[pos][sum]!=-1)
        return preCal[pos][sum];

    int way1=0;
    if(sum+availableCents[pos]<=amount)
        way1=change(pos, sum+availableCents[pos]);
    int way2=change(pos+1, sum);
    preCal[pos][sum]=way1+way2;
    return preCal[pos][sum];
}
int main()
{
    int i, j;
    while(scanf("%d", &amount)!=EOF)
    {
        for(i=0;i<5;i++)
            for(j=0;j<=amount;j++)
                preCal[i][j]=-1;
        // i also tried with memset(preCal, -1, sizeof(preCal)); this also gave TLE
        printf("%d\n", change(0,0));
    }
    return 0;
}
Or see my code here: http://pastebin.com/TP7YZVM5
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 1:07 am

Do you need to reset preCal at every test case?
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 6 (600-699)”