docker_space/frontier_cs_8/logs/gen_2.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long k;
    cin >> k;

    if (k == 1) {
        cout << 1 << "\n";
        cout << "HALT PUSH 1 GOTO 1\n";
        return 0;
    }

    long long S = (k - 1) / 2;

    int best_cost = 999;
    vector<int> best_depths;

    // Approach 1: T = S + m, try different m values
    for (int m = 1; m <= 200; m++) {
        long long T = S + m;
        if (T & 1) continue;
        if (T < 2LL * m) continue;

        vector<int> bits;
        for (int b = 1; b <= 40; b++) {
            if ((T >> b) & 1) bits.push_back(b);
        }

        int pc = (int)bits.size();
        if (pc > m) continue;

        int splits_needed = m - pc;

        multiset<int> exps(bits.begin(), bits.end());
        int cost = 0;
        for (int b : bits) cost += b;

        bool valid = true;
        for (int s = 0; s < splits_needed; s++) {
            auto it = exps.lower_bound(2);
            if (it == exps.end()) { valid = false; break; }
            int d = *it;
            exps.erase(it);
            exps.insert(d - 1);
            exps.insert(d - 1);
            cost += (d - 2);
        }

        if (!valid) continue;

        int total = cost + 1;
        if (total < best_cost && total <= 512) {
            best_cost = total;
            best_depths.clear();
            for (int e : exps) best_depths.push_back(e);
        }
    }

    // Approach 2: Greedy (largest block first)
    {
        long long remaining = S;
        int total_d = 0;
        vector<int> depths;
        while (remaining > 0) {
            int d = 1;
            while ((1LL << (d + 1)) - 1 <= remaining) d++;
            depths.push_back(d);
            total_d += d;
            remaining -= (1LL << d) - 1;
        }
        int total = total_d + 1;
        if (total < best_cost && total <= 512) {
            best_cost = total;
            best_depths = depths;
        }
    }

    int n = best_cost;
    int mm = (int)best_depths.size();

    cout << n << "\n";

    int pos = 1;
    for (int bi = 0; bi < mm; bi++) {
        int d = best_depths[bi];
        int start = pos;
        for (int j = 1; j <= d; j++) {
            cout << "POP " << j << " GOTO " << (start + j) << " PUSH " << j << " GOTO " << start << "\n";
            pos++;
        }
    }

    cout << "HALT PUSH 1 GOTO " << pos << "\n";

    return 0;
}