11137 - Ingenuous Cubrency

[DP]

Could someone check my input/output? Given below:
input:

Code: Select all

11
33
44
99
100
300
200
499
599
450
789
1000
2000
2165
3000
1111
477
7
49
679

output:

Code: Select all

2
6
9
55
35
321
141
777
1028
658
1522
2146
5638
6268
9794
2484
728
1
10
1225

all are right?
thnx

[luishhh]

no, in fact there are only 5 results ok
does your code output the right answer for the sample input?

[DP]

Thanks
Now, i got it how to solve.

[coolguy]

i guess this problem is about normal coin change problem . the algo i used is based on dp . but even the sample i/o doesnt match . i dont know wats da problem . could some one check please . the main portion of my code is as follows :

Code: Select all

        
        val[0]=0;
	for(i=1;i<=21;++i){
		val[i]=i*i*i;
	}
	for(j=0;j<=10000;++j)memo[i]=1;
	for( j = 1 ; j <= 21 ; ++j ){
		for(i=val[j];i<10001;++i){
			memo[i] += memo[i-val[j]];
		}
	}

am i doing the right thing ? please help me ...........
bye bye

[little joey]

Setting memo[22] to 1 10001 times?

[asif_rahman0]

i did it recursively. It seems easy to me.
But my program took too much time(0.x4.xx) where others took 0.00.04/06.
Can someone tell me is there any other method without DP?

[coolguy]

that was a typo

Code: Select all

       
  val[0]=0;
   for(i=1;i<=21;++i){
      val[i]=i*i*i;
   }
   for(j=0;j<=10000;++j)memo[j]=1;
   for( j = 1 ; j <= 21 ; ++j ){
      for(i=val[j];i<10001;++i){
         memo[i] += memo[i-val[j]];
      }
   } 

this version is right . but still it doesnt work . i dont know y it doesnt work . please help ...
bye bye

[nymo]

to coolguy, you need not use the following line:

Code: Select all

 for(j=0;j<=10000;++j)memo[j]=1; 

basically, you just need to init your memo array so that it works correctly for the upcoming code fragment.

Code: Select all

try memo[0] = 1; instead.

hope it works.

[asif_rahman0]

nymo also right.
But in your own code you need.....

that was a typo

Code: Select all

       
  val[0]=0;
   for(i=1;i<=21;++i){
      val[i]=i*i*i;
   }
   for(j=0;j<=10000;++j)memo[j]=1;
   for( j = 1 ; j <= 21 ; ++j ){
      for(i=val[j];i<10001;++i){
         memo[i] += memo[i-val[j]];
      }
   } 

i dont think u got your code. right??
just change j=2 instead of j=1. Because you already initialize memo[] with 1. Then again you do. So what is happing?? TRY to think then give it to board!

hope it helps

[coolguy]

to nymo :
Thanx man it works
bye bye

[annhy]

Could someone check my input/output? Given below:
input:

Code: Select all

11
33
44
99
100
300
200
499
599
450
789
1000
2000
2165
3000
1111
477
7
49
679

output:

Code: Select all

2
6
9
55
35
321
141
777
1028
658
1522
2146
5638
6268
9794
2484
728
1
10
1225

all are right?
thnx

My AC program outputs:

Code: Select all

2
6
9
39
39
683
208
3959
8015
2702
25294
73945
2789209
4446082
34188840
122148
3346
1
10
13349

Hope it helps.

[hduong]

I always got Runtime Error although I already tested every case from 1 to 9999. Could anyone help me figure out the error in my code?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		memo = new long[10030][30];
		clearMemo();
		while((line=f.readLine())!=null) {
			if(line.length()==0) continue;
			money = Integer.valueOf(line.trim());
			System.out.println(change(money,21));
		}
	}
	public static void clearMemo() {
		for(int i=0; i<memo.length; i++) {
			for(int j=0; j<memo[i].length; j++) {
				memo[i][j] = -1;
			}
		}
	}
	public static long change(int value, int m) {
		if(value<0) {
			return 0;
		}
		if(value==0) {
			return 1;
		}
		if(m<1 && value>=1) {
			return 0;
		}
		if(memo[value][m]!=-1) return memo[value][m];
		int coinValue = m*m*m;
		long ans = change(value,m-1)+change(value-coinValue,m);
		memo[value][m] = ans;
		return ans;
	}
	public static long[][] memo;
	public static int money;
}

[annhy]

I run your code on my computer and java.lang.StackOverflowError occurs. Good luck!!

I always got Runtime Error although I already tested every case from 1 to 9999. Could anyone help me figure out the error in my code?

...deleted...

[3tito]

what data type should be used in this problem ??

[brianfry713]

You can see from the sample I/O that the largest output is 440022018293, which fill fit in a 64-bit integer, but is too large for a 32-bit integer.