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
2017-07-02 21:30:32
please dont use cbrt function...gave me 10 wa's
2017-06-20 06:44:37
precompute may save you!!
2017-06-12 15:55:56
Apart from rigorous DP..
you need to optimize a bit too..
Good one ...
Hint (Try to avoid running your algo for every test case. Use your brains to optimize).
2017-05-28 17:18:24
Getting WA near test case #10 :(
2017-03-12 19:48:21
agree with you @shahzada
2017-03-10 12:32:51 shahzada
Easy dp ; Classical knapsack problem.

Last edit: 2017-03-10 12:33:24
2017-01-21 07:21:35 Kaustubh Tripathi
I am using DP approach but it's giving TLE. Can someone please help how can I optimize my code.
Submission ID: 18613501
2017-01-20 20:22:20
i guess test case #10 is not gonna let me live...damn irritating,,
2017-01-14 11:54:11
plz check my code ,,submission id 18572808
Thanks in advance

Last edit: 2017-01-14 12:27:39
2016-11-11 05:41:15
what should be range of given no.?
Re: Read carefully, all the limits of the testcases have been written there, either explicitly or implicitly :)

Last edit: 2016-11-25 14:10:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.