File size: 5,527 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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | #include <bits/stdc++.h>
using namespace std;
long long sum_tz(long long rr) {
if (rr <= 0) return 0;
long long res = 0;
for (long long p = 2; p <= rr; p <<= 1) {
res += rr / p;
}
return res;
}
int get_l(long long rr) {
if (rr == 0) return 0;
int res = 0;
long long t = rr;
while (t) {
res++;
t >>= 1;
}
return res;
}
long long total_steps(long long rr) {
if (rr == 0) return 1LL;
int ll = get_l(rr);
long long S_decr = sum_tz(rr);
long long sum_d = 4 * S_decr + 2 * rr;
long long S_ch = sum_tz(rr - 1);
long long num_nz_ch = max(0LL, rr - 1);
long long sum_ch_nz = 2 * S_ch + 4 * num_nz_ch;
long long ch_zero = 3LL * ll;
return (long long)ll + sum_d + sum_ch_nz + ch_zero + 1;
}
void generate_small(vector<string>& prog, int start, long long d) {
long long m = (d - 1) / 2;
if (m == 0) return;
if (m == 1) {
int s = start;
prog.push_back("POP 1 GOTO " + to_string(s + 1) + " PUSH 1 GOTO " + to_string(s + 1));
prog.push_back("POP 1 GOTO " + to_string(s + 2) + " PUSH 2 GOTO " + to_string(s + 2));
prog.push_back("HALT PUSH 1 GOTO " + to_string(s));
} else {
int s = start;
prog.push_back("POP 3 GOTO " + to_string(s) + " PUSH 1 GOTO " + to_string(s + 1));
prog.push_back("HALT PUSH 1 GOTO " + to_string(s + 2));
for (long long loc_i = 3; loc_i <= m; loc_i++) {
int global_i = s + loc_i - 1;
int nextg = s + loc_i;
prog.push_back("POP 3 GOTO " + to_string(s) + " PUSH 1 GOTO " + to_string(nextg));
}
for (long long loc_j = 1; loc_j <= m; loc_j++) {
int global_j = s + m + loc_j - 1;
int nextg = (loc_j < m) ? (s + m + loc_j) : (s + 1);
prog.push_back("POP 1 GOTO " + to_string(nextg) + " PUSH 99 GOTO " + to_string(s));
}
}
}
int main() {
long long k;
cin >> k;
auto sumt = sum_tz;
auto getl = get_l;
auto tot = total_steps;
long long lo = 0, hi = k * 2LL;
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
long long ts = tot(mid);
if (ts <= k && ts % 2 == 1) {
lo = mid;
} else {
hi = mid - 1;
}
}
long long r = lo;
long long ts = tot(r);
while (r >= 0 && (ts > k || ts % 2 != 1)) {
r--;
ts = tot(r);
}
long long d = k - ts + 1;
vector<string> prog;
if (r == 0) {
if (d == 1) {
prog.push_back("HALT PUSH 1 GOTO 1");
} else {
generate_small(prog, 1, d);
}
} else {
int lll = getl(r);
int curr = 1;
for (int i = 1; i <= lll; i++) {
int pos = lll - i;
int val = ((r & (1LL << pos)) != 0) ? 2 : 1;
string ln = "POP 3 GOTO 1 PUSH " + to_string(val) + " GOTO " + to_string(curr + 1);
prog.push_back(ln);
curr++;
}
int decr_s = curr;
for (int b = 0; b < lll; b++) {
int B = curr;
int B1 = B + 1;
int B_popold = B + 2;
int B_push2 = B + 3;
int B_push1 = B + 4;
int nextb = (b < lll - 1) ? (B + 5) : decr_s;
prog.push_back("POP 2 GOTO " + to_string(B_push1) + " PUSH 1 GOTO " + to_string(B1));
prog.push_back("POP 1 GOTO " + to_string(B_popold) + " PUSH 99 GOTO 1");
prog.push_back("POP 1 GOTO " + to_string(B_push2) + " PUSH 99 GOTO 1");
prog.push_back("PUSH 2 GOTO " + to_string(nextb));
prog.push_back("PUSH 1 GOTO " + to_string(decr_s));
curr += 5;
}
int check_s = curr;
int pop1_s_temp = -1; // to set later
for (int b = 0; b < lll; b++) {
int C = curr;
int C1 = C + 1;
int C_popold = C + 2;
int C_push2 = C + 3;
int C_push1 = C + 4;
int nextc = (b < lll - 1) ? (C + 5) : 0; // placeholder
prog.push_back("POP 1 GOTO " + to_string(C_push1) + " PUSH 1 GOTO " + to_string(C1));
prog.push_back("POP 1 GOTO " + to_string(C_popold) + " PUSH 99 GOTO 1");
prog.push_back("POP 2 GOTO " + to_string(C_push2) + " PUSH 99 GOTO 1");
prog.push_back("PUSH 2 GOTO " + to_string(decr_s));
string placeholder = "PUSH 1 GOTO " + to_string(nextc); // will overwrite if last
prog.push_back(placeholder);
curr += 5;
}
// now pop1
int pop1_s = curr;
bool use_sm = (d > 1);
int final_goto_temp = use_sm ? (pop1_s + lll) : (pop1_s + lll);
for (int i = 0; i < lll; i++) {
int P = curr;
int gnext_p = (i < lll - 1) ? (P + 1) : final_goto_temp;
prog.push_back("POP 1 GOTO " + to_string(gnext_p) + " PUSH 99 GOTO 1");
curr++;
}
int after_p = curr;
// set the last check push1
int last_C = check_s + 5 * (lll - 1);
int last_C_push1 = last_C + 4;
prog[last_C_push1 - 1] = "PUSH 1 GOTO " + to_string(pop1_s);
if (!use_sm) {
prog.push_back("HALT PUSH 1 GOTO " + to_string(after_p));
curr++;
} else {
generate_small(prog, after_p, d);
curr += ( ( (d-1)/2 ==1 ) ? 3 : 2 * ((d-1)/2) );
}
}
int n = prog.size();
cout << n << endl;
for (string ln : prog) {
cout << ln << endl;
}
return 0;
} |