# Check cube

quoc14
c_cpp
25 days ago
2.3 kB
1
Indexable
Never
Backtrack
```Level 4
Checking cube
Given a integer N. Find number of possible ways to represent N as a sum of at most five cubes.

Input

First line contains N.

1<=N<=125000.

Output

Output the result

Sample

Input

4
1
64
905
15436

Output
#1 1
#2 2
#3 0
#4 12

Giải thích:
+ Cách 1: 64 = 27 + 27 + 8 + 1 + 1
+ Cách 2: 64 = 64 + 0  + 0 + 0 + 0

#1 39
#2 18
#3 1
#4 12
#5 1
#6 2
#7 4
#8 8
#9 15
#10 4
#11 13
#12 8
#13 9
#14 13
#15 31
#16 24
#17 2
#18 9
#19 4
#20 10
#21 7
#22 10
#23 14
#24 8
#25 21
#26 34
#27 3
#28 17
#29 13
#30 1
#31 2
#32 3
#33 6
#34 36
#35 1
#36 16
#37 8
#38 2
#39 11
#40 7
#41 26
#42 19
#43 11
#44 23
#45 27
#46 2
#47 19
#48 2
#49 16
#50 4
Time: 1.579000000 s.

50
88236
48656
13459
11728
36174
30156
4852
20681
30537
86072
90017
117168
37756
64019
100162
43119
11136
13121
10356
78102
101127
82690
81340
62017
34651
124902
29776
82925
100821
3244
124546
38922
119326
123570
22936
103654
70963
36213
113709
69648
76626
79011
84170
119374
66214
36590
71902
4877
109837
51232

#include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, result;

int cube[51];

int maxx(int a, int b) { return (a>b ? a : b); }

int minn(int a, int b) { return (a<b ? a : b); }

void updateCubes(){
for(int i = 1; i <= 50; i++){
cube[i] = i*i*i;
}
}

void backtrack(int index, int sum, int from){
if(!sum){
result++;
return;
}
if(index == 5) return;

for(int i = from; i > 0; i--){
backtrack(index + 1, sum - cube[i], i);
}
}

int main(){

freopen("input.txt", "r", stdin);

// Calc clock
clock_t time_start, time_end;
time_start = clock();

cin >> T;
for(int tc = 1; tc <= T; tc++){
// Initial && Input
cin >> n;
result = 0;

// Solve Problem
updateCubes();
int m;
for(int i = 1; i <= 50; i++){
if(cube[i] <= n) m = i;
else break;
}
backtrack(0, n, m);

// Output
cout << "#" << tc << " " << (result) << endl;
}

// Calc Time
time_end = clock();
cout.setf(ios::fixed);
cout.precision(9);
cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;

return 0;
}```