CUBNUM - Cube Numbers

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

  • n = 5, n = 13 + 13 + 13 + 13 + 13 (m = 5)
  • n = 8, n = 23 (m = 1)
  • n = 35, n = 23 + 33 (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 ≤ 105). Input is terminated by end of file (EOF).
It is guaranteed that total test case per input file is less than 105.

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 ≤ 105) 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

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

hide comments
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
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
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
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
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
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
2016-08-31 16:19:40 Bhumit
@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
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
2016-08-22 22:30:01
@hanstan can you please check my code. I can't understand why i am getting wrong answers.
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.