Page 5 of 6

Re: 674 - Coin Change

Posted: Fri Dec 19, 2008 10:17 pm
by mf
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)

Runtime error

Posted: Fri Dec 19, 2008 11:20 pm
by mimi
I change it.But now it says Runtime error?? :oops:

Re: 674 - Coin Change

Posted: Fri Dec 19, 2008 11:34 pm
by mf
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.

Re: 674 - Coin Change

Posted: Sat Dec 20, 2008 12:18 am
by mimi
-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:

Re: 674 - Coin Change

Posted: Sat Dec 20, 2008 12:34 am
by mf

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]);
 }
 }

Re: 674 - Coin Change

Posted: Sat Dec 20, 2008 12:44 am
by mimi
Thank you mf!!! :D My code is accepted now.

674 - Coin Change

Posted: Thu Jan 29, 2009 10:27 pm
by sazzadcsedu
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???

Re: 674 - Coin Change

Posted: Fri Jan 30, 2009 9:34 pm
by newkid
@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..

Re: 674 - Coin Change

Posted: Thu Apr 01, 2010 10:43 am
by KRUNCH
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

Re: 674 - Coin Change

Posted: Thu Apr 01, 2010 10:36 pm
by helloneo
There is a simple test case your code doesn't pass..

input:
5

output should be
2

You can try to reason out..

Re: 674 - Coin Change

Posted: Fri Apr 02, 2010 9:35 am
by KRUNCH
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 -.-'

Re: 674 - Coin Change

Posted: Fri Dec 10, 2010 1:02 pm
by viharvera
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?

Re: 674 - Coin Change

Posted: Fri May 25, 2012 7:29 pm
by fsafs168
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

Re: 674 - Coin Change

Posted: Sat Jan 10, 2015 7:05 pm
by Shahidul.CSE
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

Re: 674 - Coin Change

Posted: Tue Jan 13, 2015 1:07 am
by brianfry713
Do you need to reset preCal at every test case?