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
kspoj: 2017-11-22 15:36:33

I'm getting WA at testcase #10 :(
I've tried most testacses from spoj toolkit, and my code is fine with them.
Can someone please suggest some testcases where my code might fail.
BTW I'm using bottom up DP to precompute all answers

Re: Lucky you I still found your submission.
Actually you are getting WA at the sample output given above XD.
Read the question carefully please.
(Spoiler alert: Whitespace is a thing XD)

Last edit: 2017-12-05 11:00:43
aditya_rev: 2017-11-18 22:03:41

Precompute should works. But why getting WA ? :(

Re: Well I'm not sure but yours got WA on TC 4 XD.
Maybe there are some errors during conversion or maybe flawed logic?

Last edit: 2017-12-05 11:10:53
draco_malfoy: 2017-09-27 17:16:19

@hanstan can you please help me with my solution no 20241014?Getting WA.
Thank you in advance.

Re: Seems flawed logic since you got WA on first test case tho.
Thank you.
Figured it out :)

Last edit: 2018-01-13 22:13:22
rayhan50001: 2017-08-14 13:35:34

Cbrt cost me 3 WA.
my best 0.11
Easy DP.
try to precompute.

Last edit: 2017-08-14 13:57:01
namitp: 2017-08-13 12:56:19

Very Easy Nailed It in one Go....

viratian_070: 2017-07-02 21:30:32

please dont use cbrt function...gave me 10 wa's

sandeep_4141: 2017-06-20 06:44:37

precompute may save you!!

rishabhm123: 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).

a2j007: 2017-05-28 17:18:24

Getting WA near test case #10 :(

rajeev_899: 2017-03-12 19:48:21

agree with you @shahzada


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