// yukicoder: 873 バイナリ、ヤバいなり!w // 2019.8.31 bal4u #include #include #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void outs(char *s) { while (*s) pc(*s++); } #define INF 0x01010101 #define LIM 555 int N; int a[LIM]; int w; int dp[300005]; char s01[LIM]; int last = '1'; void pr(int w) { static char *s = s01; last = s[w], s[w] = 0; outs(s); s[w] = last; s = (last == '0')? s01+1: s01; } int adv(int odd, int k) { int i; for (i = 2-odd; i <= w && a[i] <= k; i+=2) { if (dp[k] == dp[k-a[i]] + i) { k -= a[i], pr(i); return k; } } return -1; } int rev(int odd, int k) { int i = w; if ((i & 1) ^ odd) i--; while (i > 0 && a[i] > k) i -= 2; for ( ; i > 0; i-=2) { if (dp[k] == dp[k-a[i]] + i) { k -= a[i], pr(i); return k; } } return -1; } inline static void chmin(int *a, int b) { if (*a > b) *a = b; } int main() { int i, j, k; N = in(); if (N == 1) { puts("0"); return 0; } w = 0; while (w*w <= N) w++, a[w] = w*w; i = 0; while (i < LIM) s01[i++] = '0', s01[i++] = '1'; memset(dp, INF, sizeof(dp)); dp[0] = 0; for (j = 1; j <= N; j++) { for (i = 1; a[i] <= j; i++) chmin(&dp[j], dp[j-a[i]] + i); } k = N; while (k > 0) { if (last == '1') { for (i = 1; i <= w && a[i] <= k; i+=2) { while (a[i] <= k && dp[k] == dp[k-a[i]] + i) { k -= a[i], pr(i); } } k = rev(0, k); } else { if ((j = adv(0, k)) >= 0) k = j; else k = rev(1, k); } } pc('\n'); return 0; }