#include #include #include #include using namespace std; #define MAX (1LL<<32) long long get(long long i); long long compute(long long i) { // Pell numbers switch (i) { case 0: return 0LL; case 1: return 1LL; case 2: return 2LL; case 3: return 5LL; case 4: return 12LL; case 5: return 29LL; case 6: return 70LL; case 7: return 169LL; case 8: return 408LL; case 9: return 985LL; case 10: return 2378LL; case 11: return 5741LL; case 12: return 13860LL; case 13: return 33461LL; case 14: return 80782LL; case 15: return 195025LL; case 16: return 470832LL; case 17: return 1136689LL; case 18: return 2744210LL; case 19: return 6625109LL; case 20: return 15994428LL; case 21: return 38613965LL; case 22: return 93222358LL; case 23: return 225058681LL; case 24: return 543339720LL; case 25: return 1311738121LL; case 26: return 3166815962LL; case 27: return 7645370045LL; case 28: return 18457556052LL; case 29: return 44560482149LL; case 30: return 107578520350LL; case 31: return 259717522849LL; default: exit(1); } } vector f; long long get(long long i) { while (i>=f.size()) { f.push_back(compute(f.size())); } return f[i]; } int main() { bool *sums = new bool[MAX]; memset(sums, 0, MAX*sizeof(*sums)); sums[0] = true; long long total = 0; long long limit = 0; long long n = 0; for (long long v=1;; v++) { while (get(limit) < v+total) { limit++; } bool keep = true; long long d; for (long long t=limit; (d=get(t)-v)>=0; t--) { if (d=0; o--) { if (sums[o]) { if (o+v>=MAX) { delete[] sums; return 0; } sums[o+v] = true; } } total += v; } } }