#define _USE_MATH_DEFINES #include using namespace std; const int m = 303030; vector dp(m, 1 << 30); vector v; string ans = "2"; int n; void make_ans() { deque use[2]; for (int i : v) { use[i % 2].push_back(i); //cerr << i << " "; } //cerr << endl; string s; for (int i : use[1]) for (int j = 0; j < i; j++) s += (j % 2 + '0'); int it = 0; while (use[0].size()) { if (it % 2 == 0) { for (int j = 0; j < use[0].back(); j++) s += (j % 2 + '0'); use[0].pop_back(); } else { for (int j = 0; j < use[0].front(); j++) s += (1 - (j % 2) + '0'); use[0].pop_front(); } it++; } ans = min(ans, s); } void dfs (int cur, int len) { if (cur == n) { make_ans(); return; } if (cur + len * len > n) return; if (dp[cur] + len + dp[n - (cur + len * len)] == dp[n]) { //cerr << cur << " " << len << endl; v.push_back(len); dfs(cur + len * len, len); v.pop_back(); } dfs(cur, len + 1); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; dp[0] = 0; for (int i = 0; i < m; i++) { for (int j = 1; i + j * j < m; j++) { dp[i + j * j] = min(dp[i + j * j], dp[i] + j); } } dfs(0, 1); cout << ans << endl; return 0; }