Square into Squares. Protect trees!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
class Decomp
{
public:
static std::vector<long long> decompose(long long n);
};
bool can(long long x, long long ma) {
return x * (x + 1) * (2 * x + 1) / 6 >= ma;
}
bool helper(vector<long long>& res, long long limit, long long x) {
if(x == 0) return true;
limit = min(limit, (long long)sqrt(x));
while(limit and can(limit, x)) {
res.push_back(limit);
if(helper(res, limit - 1, x - limit * limit)) return true;
res.pop_back();
limit -= 1;
}
return false;
}
vector<long long> Decomp::decompose(long long n) {
long long x = n - 1;
while(x) {
vector<long long> res{x};
helper(res, x - 1, (n + x) * (n - x));
if(res.size() == 1) x -= 1;
else {
reverse(begin(res), end(res));
return res;
}
}
return {};
}
|
