#include <bitset> #include <iostream> #include <stdlib.h> #include <vector> using namespace std; #define MAX (1LL<<34) bitset<MAX> *seen = 0; vector<long long> cc; long long avoid(long long p) { if (!seen->test(0)) { return 0; } long long w=1; for (long long b=1;; b<<=1) { if ((p & b)==0) { if (cc.size()==w) { cc.resize(2*w); } for (long long k=0; k<w; k++) { long long c = cc[w+k] = b + cc[k]; if (c >= MAX) { exit(1); } if (!seen->test(c)) { return c; } } w*=2; } } } #define WANTED (1LL<<14) long long a[WANTED]; long long u = 0; int main() { seen = new bitset<MAX>; cc.push_back(0); for (long long n=0; n<WANTED; n++) { a[n]=-1; } long long pp=0; long long p=0; for (long long n=0; u<WANTED; n++) { long long v=avoid(pp+p); seen->set(v); if (v<WANTED) { a[v] = n; while (u<WANTED && a[u]>=0) { cout << u << ' ' << a[u] << endl; u++; } } pp=p; p=v; } delete seen; seen = 0; return 0; }