SPOJ.com - Problem CUBNUM

CUBNUM - Cube Numbers

For any positive integer n, n can be represented as sum of other positive cube numbers (n = a₁³ + a₂³ + ... + a_m³). Your task is to print the smallest m, where m is number of cube numbers used to form n, such that n = a₁³ + a₂³ + ... + a_m³. For example:

n = 5, n = 1³ + 1³ + 1³ + 1³ + 1³ (m = 5)
n = 8, n = 2³ (m = 1)
n = 35, n = 2³ + 3³ (m = 2)

Note: My fastest time is 0.09s :).
Edit: My fastest time is 0.05s now lol
My Java solution is also accepted.

Input

Input consists of several test cases separated by new lines. Each test case consists of a positive integer, denoting the number of n (1 ≤ n ≤ 10⁵). Input is terminated by end of file (EOF).
It is guaranteed that total test case per input file is less than 10⁵.

Note: For c++ users, you can use while(scanf("%d",&n)!=EOF); to read input until EOF.
Warning: large Input/Output data, be careful with certain languages!.

Output

For each case, print "Case #X: M", where X (1 ≤ X ≤ 10⁵) is the case number, and M is the minimum cube numbers used to form the integer n. There must be no trailing spaces at the end of printed lines, neither empty characters. Print a newline after each testcase.

Example

Input:
1
2
5
8
35

Output:
Case #1: 1
Case #2: 2
Case #3: 5
Case #4: 1
Case #5: 2

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	helig_123: 2016-10-24 16:33:37 Knapsack problem, got AC after 3 submits Re: Actually I created a classical dp with simple math tho.... Last edit: 2016-11-25 14:10:59
	cubalgo: 2016-10-11 07:49:35 @hanstan pls check my code. Submission id:17904554 Re: Somehow your code fails the very small and large input ones Try to check it out... Last edit: 2016-11-25 14:23:19
	goelnandan: 2016-10-10 17:50:16 submission id:17900280 whats wrong with my code :\ edited: was also checking extra if condition for only very less cases. Last edit: 2016-10-11 06:56:17
	dwij28: 2016-10-04 22:01:08 I am using DP, have manually checked for several testcases and I am still getting a WA. Can't see what is wrong with my solution. :/ Got AC finally in 9th attempt. Cannot believe this. The reasons for my WA were that (int) cbrt(3375) gives 14 instead of 15. Further even upper_bound and lower_bound in STL failed for me. Had to use linear search. Found out my mistake by doing a vimdiff on 2 textfiles, one with linear search and other with (int) cbrt(n). Feeling like a pro. :D Re: Well, we need simple math to solve this aswell XD Last edit: 2016-10-07 14:26:43
	singhsauravsk: 2016-10-03 16:59:58 @hanstan : could you please give a test case where my submission number 17842980 fails to give expected output. It would be very nice of you. Re: Acutally, once I give any of the input and output of the problem I think you would certainly know what is wrong XD. Well I'll just give a testcase since I am a nice person :P. The answer for 87072 is 4. Last edit: 2016-10-04 16:21:05
	ashwin9686: 2016-09-14 01:56:55 @hanstan As suggested I have checked all the answers from 1 to 100 using brute force and my code is running right on all of them. I still don't get what I am doing wrong. Re: It means your brute force is missing something to be checked. Make sure you try all of the possible combinations. Even 99 can be obtained by 1^3+1^3+... or 3^3+2^3+1^3+1^3+1^3+... and others :) Another spoiler: Your approach was greedy not dp so it would certainly gave a WA Last edit: 2016-09-15 16:13:42
	Bhumit: 2016-08-31 16:19:40 @hanstan Please check my code. I am getting WA in Java. Submission ID: 17626737 (Going with greedy approach.) Re: To all the ones who are also getting a wrong answer, It is a dp problem, it can't be done by any greedy solution. I did not put the dp tag just for decoration --'. Last edit: 2016-09-09 15:01:10
	kaumil_97: 2016-08-29 15:41:06 @hanstan pls check my code Re: Please check the desired output. Last edit: 2016-09-09 14:59:20
	harshgupta007: 2016-08-22 22:30:01 @hanstan can you please check my code. I can't understand why i am getting wrong answers.
	tarungupta1956: 2016-08-05 22:21:49 @hanstan pls check my code once.. Re: First, you forgot to print the case number. Second, your logic is wrong. See my suggestion below :). Last edit: 2016-08-11 10:16:08

Submit solution!

Added by:	hanstan
Date:	2016-06-21
Time limit:	0.200s-3s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 GOSU JS-MONKEY
Resource:	Self