| #include <bits/stdc++.h> |
| using namespace std; |
|
|
| int main() { |
| long long k; |
| cin >> k; |
| if (k == 1) { |
| cout << 1 << endl; |
| cout << "HALT PUSH 1 GOTO 1" << endl; |
| return 0; |
| } |
| long long m = (k - 1) / 2; |
| if (k <= 513) { |
| |
| if (m == 1) { |
| cout << 3 << endl; |
| cout << "POP 2 GOTO 1 PUSH 1 GOTO 2" << endl; |
| cout << "POP 1 GOTO 3 PUSH 2 GOTO 3" << endl; |
| cout << "HALT PUSH 1 GOTO 3" << endl; |
| } else { |
| int n = 2 * m; |
| cout << n << endl; |
| int wrong = 2, b = 1; |
| int halt_pos = m; |
| |
| for (int i = 1; i <= m; i++) { |
| if (i == m) { |
| cout << "HALT PUSH " << b << " GOTO " << (m + 1) << endl; |
| } else { |
| cout << "POP " << wrong << " GOTO " << i << " PUSH " << b << " GOTO " << (i + 1) << endl; |
| } |
| } |
| |
| for (int j = 1; j <= m; j++) { |
| int pos = m + j; |
| int next_pos = (j < m ? m + j + 1 : halt_pos); |
| cout << "POP " << b << " GOTO " << next_pos << " PUSH " << wrong << " GOTO " << pos << endl; |
| } |
| } |
| return 0; |
| } |
| |
| vector<int> zero_sym(31), one_sym(31); |
| for (int i = 0; i < 31; i++) { |
| zero_sym[i] = 2 * i + 1; |
| one_sym[i] = 2 * i + 2; |
| } |
| int temp_sym = 1024; |
| int wrong_a = 1023; |
| int added_b = 64; |
| |
| long long low = 0, high = (1LL << 31) - 1; |
| long long best_mm = 0; |
| while (low <= high) { |
| long long mid = low + (high - low) / 2; |
| long long sumt = 0; |
| for (int kk = 1; kk <= 31; kk++) { |
| sumt += (mid >> kk); |
| } |
| long long gg = 31LL + 4 * sumt + 4 * mid + 124LL + 31LL; |
| if (gg <= k - 1) { |
| best_mm = mid; |
| low = mid + 1; |
| } else { |
| high = mid - 1; |
| } |
| } |
| long long mm = best_mm; |
| |
| vector<int> bit_val(31); |
| for (int i = 0; i < 31; i++) { |
| bit_val[i] = ((mm & (1LL << i)) ? one_sym[i] : zero_sym[i]); |
| } |
| |
| long long sumt = 0; |
| for (int kk = 1; kk <= 31; kk++) { |
| sumt += (mm >> kk); |
| } |
| long long g = 31LL + 4 * sumt + 4 * mm + 124LL + 31LL; |
| long long ee = k - g - 1; |
| int l = ee / 2; |
| |
| int pos = 1; |
| vector<int> setup_pos(31); |
| for (int i = 0; i < 31; i++) setup_pos[i] = pos++; |
| vector<int> a_pos(31), b_pos(31), c_pos(31); |
| for (int i = 0; i < 31; i++) { |
| a_pos[i] = pos++; |
| b_pos[i] = pos++; |
| c_pos[i] = pos++; |
| } |
| vector<int> p1_pos(30); |
| for (int i = 0; i < 30; i++) p1_pos[i] = pos++; |
| vector<int> p0_pos(31); |
| for (int i = 0; i < 31; i++) p0_pos[i] = pos++; |
| int push_temp_p = pos++; |
| int pop_temp_p = pos++; |
| vector<int> under_p_pos(31); |
| pos--; |
| for (int i = 30; i >= 0; i--) { |
| under_p_pos[i] = pos++; |
| } |
| vector<int> clean_p_pos(31); |
| for (int i = 0; i < 31; i++) clean_p_pos[i] = pos++; |
| vector<int> add_push(l), add_pop(l); |
| for (int jj = 0; jj < l; jj++) { |
| add_push[jj] = pos++; |
| add_pop[jj] = pos++; |
| } |
| int h_pos = pos++; |
| int total_n = h_pos; |
| |
| vector<string> prog(total_n + 1); |
| |
| for (int ii = 0; ii < 31; ii++) { |
| int bb = 30 - ii; |
| int p = setup_pos[ii]; |
| int s = bit_val[bb]; |
| int nxt = (ii < 30 ? setup_pos[ii + 1] : a_pos[0]); |
| prog[p] = "POP " + to_string(wrong_a) + " GOTO 1 PUSH " + to_string(s) + " GOTO " + to_string(nxt); |
| } |
| |
| int done_p = push_temp_p; |
| for (int i = 0; i < 31; i++) { |
| int ap = a_pos[i]; |
| int ones = one_sym[i]; |
| int was1p = p0_pos[i]; |
| int bp = b_pos[i]; |
| int cp = c_pos[i]; |
| int zeros = zero_sym[i]; |
| int was0p = (i < 30 ? a_pos[i + 1] : under_p_pos[30]); |
| prog[ap] = "POP " + to_string(ones) + " GOTO " + to_string(was1p) + " PUSH " + to_string(temp_sym) + " GOTO " + to_string(bp); |
| prog[bp] = "POP " + to_string(temp_sym) + " GOTO " + to_string(cp) + " PUSH " + to_string(wrong_a) + " GOTO 1"; |
| prog[cp] = "POP " + to_string(zeros) + " GOTO " + to_string(was0p) + " PUSH " + to_string(wrong_a) + " GOTO 1"; |
| } |
| |
| prog[p1_pos[0]] = "POP " + to_string(wrong_a) + " GOTO 1 PUSH " + to_string(one_sym[0]) + " GOTO " + to_string(done_p); |
| for (int j = 1; j < 30; j++) { |
| prog[p1_pos[j]] = "POP " + to_string(wrong_a) + " GOTO 1 PUSH " + to_string(one_sym[j]) + " GOTO " + to_string(p1_pos[j - 1]); |
| } |
| |
| for (int i = 0; i <= 30; i++) { |
| int nextp = (i == 0 ? done_p : p1_pos[i - 1]); |
| int zs = zero_sym[i]; |
| prog[p0_pos[i]] = "POP " + to_string(wrong_a) + " GOTO 1 PUSH " + to_string(zs) + " GOTO " + to_string(nextp); |
| } |
| |
| prog[push_temp_p] = "POP 3 GOTO 1 PUSH " + to_string(temp_sym) + " GOTO " + to_string(pop_temp_p); |
| prog[pop_temp_p] = "POP " + to_string(temp_sym) + " GOTO " + to_string(a_pos[0]) + " PUSH " + to_string(wrong_a) + " GOTO 1"; |
| |
| int clean_start_pos = clean_p_pos[0]; |
| for (int i = 30; i >= 0; i--) { |
| int p = under_p_pos[i]; |
| int zs = zero_sym[i]; |
| int nxt = (i > 0 ? under_p_pos[i - 1] : clean_start_pos); |
| prog[p] = "POP " + to_string(wrong_a) + " GOTO 1 PUSH " + to_string(zs) + " GOTO " + to_string(nxt); |
| } |
| |
| int added_or_h = (l == 0 ? h_pos : add_push[0]); |
| for (int i = 0; i < 31; i++) { |
| int p = clean_p_pos[i]; |
| int zs = zero_sym[i]; |
| int nxt = (i < 30 ? clean_p_pos[i + 1] : added_or_h); |
| prog[p] = "POP " + to_string(zs) + " GOTO " + to_string(nxt) + " PUSH " + to_string(wrong_a) + " GOTO 1"; |
| } |
| |
| int prev_n = h_pos; |
| for (int jj = l - 1; jj >= 0; jj--) { |
| int popp = add_pop[jj]; |
| prog[popp] = "POP " + to_string(added_b) + " GOTO " + to_string(prev_n) + " PUSH " + to_string(wrong_a) + " GOTO 1"; |
| int pushp = add_push[jj]; |
| prog[pushp] = "POP " + to_string(wrong_a) + " GOTO 1 PUSH " + to_string(added_b) + " GOTO " + to_string(popp); |
| prev_n = pushp; |
| } |
| |
| prog[h_pos] = "HALT PUSH 1 GOTO " + to_string(h_pos); |
| |
| cout << total_n << endl; |
| for (int i = 1; i <= total_n; i++) { |
| cout << prog[i] << endl; |
| } |
| return 0; |
| } |
