//include //------------------------------------------ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";} #define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}} using LL = long long; //------------------------------------------ //------------------------------------------ constexpr LL INF = 1e15; constexpr LL MAX_N = 300030; int main() { LL N; cin >> N; vector> cand; for (LL i = 1; i * i <= MAX_N; i++) cand.push_back(make_pair(i, i * i)); vector dp(MAX_N + 10, INF); vector prev(MAX_N + 10, INF); dp[0] = 0; for (LL i = 1; i <= MAX_N; i++) { for (int j = 0; j < cand.size(); j++) { LL d = cand[j].first; LL dd = cand[j].second; if (i - dd >= 0) { if (dp[i] > dp[i - dd] + d) { dp[i] = dp[i - dd] + d; prev[i] = d; } else if (dp[i] == dp[i - dd] + d) { if (d % 2) { dp[i] = dp[i - dd] + d; prev[i] = d; } } } } } LL D = N; vector len; while (D != 0) { len.push_back(prev[D]); D -= prev[D] * prev[D]; } vector odd, even; for (int i = 0; i < len.size(); i++) { if (len[i] % 2) odd.push_back(len[i]); else even.push_back(len[i]); } sort(odd.begin(), odd.end()); sort(even.begin(), even.end()); string ans = ""; LL now = 0; for (int i = 0; i < odd.size(); i++) { LL d = odd[i]; for (LL j = 0; j < d; j++) { ans += ('0' + now); if (j != d - 1) { now = 1 - now; } } } for (int i = 0; i < even.size(); i++) { LL d = even[i]; for (LL j = 0; j < d; j++) { ans += ('0' + now); if (j != d - 1) { now = 1 - now; } } } cout << ans << endl; // SHOW_VECTOR(dp); // SHOW_VECTOR(prev); }