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
2021-06-08 05:23:34 Rafail Loizou
His input files have end of line so be careful with that always check you haven't reached end of file before printing the answer (i.e. the last integer will be read twice because of the end line character).
2020-08-28 13:22:20
never use cbrt or any mathematical func here!! costed me 7 wa:(
2018-09-21 20:51:26
i tried binary_search(greedy)+dp ,but failed at test 10.
then, only dp =>passed
lol...

Last edit: 2018-09-21 20:52:51
2018-08-09 08:56:08
good dp problem!!
2018-03-25 14:03:58
The value of the number for which the sum is to be found is always less than 10^5 right?
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)

Re: @hanstan I'm printing exactly as you've specified. I also tried including a newline at the end of my output. I'm still getting WA at test case 10 :(

Last edit: 2018-06-12 16:17:34
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
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
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
2017-08-13 12:56:19
Very Easy Nailed It in one Go....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.