674 - Coin Change

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

Here's my diff:

--- 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 · Post by **mimi** » Fri Dec 19, 2008 11:20 pm

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

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

mf · 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 · Post by **mimi** » Sat Dec 20, 2008 12:44 am

Thank you mf!!!

My code is accepted now.

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

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

KRUNCH · 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

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

helloneo · 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 · 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 · 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 · 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 · 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

brianfry713 · Post by **brianfry713** » Tue Jan 13, 2015 1:07 am

Do you need to reset preCal at every test case?

OJ Board

674 - Coin Change

Re: 674 - Coin Change

Runtime error

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change

Re: 674 - Coin Change