#include <limits.h> #include <stdio.h> #include <string.h> #define MAX 13LL #define WIDTH (1LL<<MAX) // 2-adic valuation of n (A007814) long long _val2(long long n) { long long v = 0; while (n%2==0) { v++; n /= 2; } return v; } long long val2[WIDTH]; void initVal2() { val2[0] = LLONG_MAX; // infinite / not used for (long long n=1; n<sizeof(val2)/sizeof(val2[0]); n++) { val2[n] = _val2(n); } } // vertical + horizontal lines at some grid point // 0 = no line struct HV { long long hori; long long vert; }; // diagonal struct Diagonal { HV diag[WIDTH]; // by X-coordinate }; Diagonal state[2]; // we need one or two diagonals at some time int main() { initVal2(); // bottom left corner state[0].diag[0].hori = 1; state[0].diag[0].vert = 1; printf("0 1\n"); // expand for (long long x0=1; x0<WIDTH; x0++) { size_t hcut = 0; size_t vcut = 0; Diagonal &prv = state[(x0+1)%2]; // previous diagonal Diagonal &cur = state[ x0 %2]; // current diagonal for (long long x=x0, y=0; x>=0; x--, y++) { long long v = 2*val2[x] + 3; long long h = 2*val2[y] + 2; long long nx = 2*MAX-2-2*val2[x]; long long ny = 2*MAX-1-2*val2[y]; if (x==0) { // left border cur.diag[x].hori = h; cur.diag[x].vert = 1; hcut++; } else if (y==0) { // bottom border cur.diag[x].hori = 1; cur.diag[x].vert = v; vcut++; } else { long long ph = prv.diag[x-1].hori; long long pv = prv.diag[x ].vert; if (ph==0) { if (pv==0) { cur.diag[x].hori = 0; cur.diag[x].vert = 0; } else { if (h<pv) { cur.diag[x].hori = h; hcut++; } else { cur.diag[x].hori = 0; } cur.diag[x].vert = pv; } } else { if (pv==0) { cur.diag[x].hori = ph; if (v<ph) { cur.diag[x].vert = v; vcut++; } else { cur.diag[x].vert = 0; } } else { if (pv>ph) { cur.diag[x].hori = 0; cur.diag[x].vert = pv; } else { cur.diag[x].hori = ph; cur.diag[x].vert = 0; } } } } } printf("%lld %lld\n", x0, hcut); fflush(stdout); } return 0; }