File size: 2,431 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #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;
}
|