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

hide comments
priyanshukm_17: 2016-07-05 13:22:21

@hanstan pls see what is wrong with my code ....i dont think my logic is wrong !!
RE: Actually yes your logic is wrong. Try to look for some other numbers.You should try to check from 1 to 100 manually, or create a program to brute-force and check every possible combinations to check your program is correct or not.

Last edit: 2016-07-06 13:33:46
pvsmpraveen: 2016-07-02 10:35:28

Nice Dp!

Vipul Srivastava: 2016-07-02 09:19:49

Ya sorry for the stupid question.. my mistake :)

Sushovan Sen: 2016-07-02 09:07:38

I think that is clear from given test case:
Answer for 5 is : 1^3+1^3+1^3+1^3+1^3 not 2^3 + (-1)^3 + (-1)^3 + (-1)^3

Vipul Srivastava: 2016-07-02 09:00:40

a1, a2, a3 have to be positive right??


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