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)
Edit: My fastest time is 0.05s now lol
My Java solution is also accepted.
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!.
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.
Input: 1 2 5 8 35 Output: Case #1: 1 Case #2: 2 Case #3: 5 Case #4: 1 Case #5: 2
i tried binary_search(greedy)+dp ,but failed at test 10.
good dp problem!!
The value of the number for which the sum is to be found is always less than 10^5 right?
I'm getting WA at testcase #10 :(
Precompute should works. But why getting WA ? :(
@hanstan can you please help me with my solution no 20241014?Getting WA.
Cbrt cost me 3 WA.
Very Easy Nailed It in one Go....
please dont use cbrt function...gave me 10 wa's
precompute may save you!!