#include #include using namespace std; typedef long long ll; // 1.5e8なので微妙 int main(){ int n; cin >> n; vector v; for(int i = 1; i*i <= n; i++) v.push_back(i*i); int num = v.size(); vector> dp(num+1, vector(n+1, 1<<30)); dp[0][0] = 0; for(int i = 0; i < num; i++){ for(int j = 0; j <= n; j++){ dp[i+1][j] = min(dp[i+1][j], dp[i][j]); if(j >= v[i]) dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-v[i]]+i+1); } } int h = num, w = n; vector odd, even; while(w > 0){ if(w >= v[h-1] && dp[h][w] == dp[h][w-v[h-1]]+h){ w -= v[h-1]; if(h%2 == 0) even.push_back(h); else odd.push_back(h); }else{ h--; } } string ans = ""; int bef = 1; for(int o : odd){ bef = 1-bef; for(int j = 0; j < o; j++) ans += (char)('0'+bef), bef = 1-bef; } for(int e : even){ bef = 1-bef; for(int j = 0; j < e; j++) ans += (char)('0'+bef), bef = 1-bef; } cout << ans << endl; return 0; }