#include #if MYDEBUG #include "lib/cp_debug.hpp" #else #define DBG(...) ; #endif #if __cplusplus <= 201402L template T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); } template T lcm(T a, T b) { return a / gcd(a, b) * b; } #endif using LL = long long; constexpr LL LINF = 334ll << 53; constexpr int INF = 15 << 26; constexpr LL MOD = 1E9 + 7; namespace Problem { using namespace std; class Solver { public: int n; vector> dp; vector> lens; Solver(LL n) : n(n), dp((int)ceil(sqrt(n)) + 1, vector(n + 1, 30000)){}; void dfs(int largest, int sum, deque path) { DBG(largest, sum, path) if (largest == 0 && sum == 0) { lens.push_back(path); return; } int d1 = dp[largest - 1][sum]; int d2 = sum >= largest * largest ? dp[largest][sum - largest * largest] + largest : 30000; if (d1 == dp[largest][sum]) { dfs(largest - 1, sum, path); } if (d2 == dp[largest][sum]) { path.push_back(largest); dfs(largest, sum - largest * largest, path); } } void solve() { int m = dp.size() - 1; LL ub = 0; dp[0][0] = 0; for (int i = 1; i <= m; ++i) { ub += 3 * i * i; for (int j = 0; j <= min(n, ub); ++j) { dp[i][j] = dp[i - 1][j]; if (j - i * i >= 0) { dp[i][j] = min(dp[i][j], dp[i][j - i * i] + i); } } } for (int i = 2; i <= m; ++i) { for (int j = 0; j <= n; ++j) { if (dp[i][j] > dp[i - 1][j]) DBG(i, j) } } dfs(m, n, {}); DBG(lens) vector anss; for (auto ans : lens) { sort(ans.begin(), ans.end(), [&](int x, int y) -> bool { return (x % 2 > y % 2) || (x % 2 == y % 2 && x < y); }); vector len; while (!ans.empty() && ans.front() % 2 == 1) { len.push_back(ans.front()); ans.pop_front(); } int cnt = 0; while (!ans.empty()) { if (cnt % 2 == 0) { len.push_back(ans.back()); ans.pop_back(); } else { len.push_back(ans.front()); ans.pop_front(); } cnt++; } DBG(len) int c = 0; string ret = ""; for (auto z : len) { for (int i = 0; i < z; ++i) { ret.push_back('0' + c); c ^= 1; } c ^= 1; } anss.push_back(ret); } sort(anss.begin(), anss.end()); cout << anss[0] << endl; } }; // namespace Problem } // namespace Problem int main() { std::cin.tie(0); std::ios_base::sync_with_stdio(false); // std::cout << std::fixed << std::setprecision(12); long long n = 0; std::cin >> n; Problem::Solver sol(n); sol.solve(); return 0; }