#include #define VERBOSE 0 #define PLUS S[si - 1] += S[si], --si, OP.push_back("+") #define MULTIPLY S[si - 1] *= S[si], --si, OP.push_back("*") #define SWAP std::swap(S[si], S[si - 1]), OP.push_back("SWAP") #define DUP S[si + 1] = S[si], ++si, OP.push_back("DUP") #define OVER S[si + 1] = S[si - 1], ++si, OP.push_back("OVER") #define ROT std::swap(S[si], S[si - 2]), std::swap(S[si - 1], S[si - 2]), OP.push_back("ROT") #define DROP --si, OP.push_back("DROP") #define MSBL(x_) (uint64_t{1} << (uint64_t{64} - std::countl_zero(x_) - 1)) uint64_t S[10000]; auto si = 0; std::vector OP; // Jump assumptions: // - Stack is [L, 2] when entering void make_jump2() { DUP; // [.., 2, 2] MULTIPLY; // [.., 4] } void make_jump3() { DUP; // [.., 2, 2] make_jump2(); // [.., 2, 4] MULTIPLY; // [.., 8] } void make_jump4() { make_jump2(); // [.., 4] DUP; // [.., 4, 4] MULTIPLY; // [.., 16] } void make_jump5() { DUP; // [.., 2, 2] make_jump4(); // [.., 2, 16] MULTIPLY; // [.., 32] } void make_jump6() { make_jump3(); // [.., 8] DUP; // [.., 8, 8] MULTIPLY; // [.., 64] } void make_jump7() { DUP; // [.., 2, 2] make_jump6(); // [.., 2, 64] MULTIPLY; // [.., 128] } void make_jump8() { make_jump4(); // [.., 16] DUP; // [.., 16, 16] MULTIPLY; // [.., 256] } void make_jump9() { DUP; // [.., 2, 2] make_jump8(); // [.., 2, 256] MULTIPLY; // [.., 512] } void make_jump10() { make_jump5(); // [.., 32] DUP; // [.., 32, 32] MULTIPLY; // [.., 1024] } void make_jump11() { DUP; // [.., 2, 2] make_jump10(); // [.., 2, 1024] MULTIPLY; // [.., 2048] } void make_jump12() { make_jump6(); // [.., 64] DUP; // [.., 64, 64] MULTIPLY; // [.., 4096] } void make_jump13() { DUP; // [.., 2, 2] make_jump12(); // [.., 2, 4096] MULTIPLY; // [.., 8192] } void make_jump14() { make_jump7(); // [.., 128] DUP; // [.., 128, 128] MULTIPLY; // [.., 16384] } void make_jump15() { make_jump5(); // [.., 32] DUP; // [.., 32, 32] DUP; // [.., 32, 32, 32] MULTIPLY; // [.., 32, 1024] MULTIPLY; // [.., 32768] } void make_jump16() { make_jump8(); // [.., 256] DUP; // [.., 256, 256] MULTIPLY; // [.., 65536] } void make_jump17() { DUP; // [.., 2, 2] make_jump16(); // [.., 2, 65536] MULTIPLY; // [.., 131072] } void make_jump18() { make_jump9(); // [.., 512] DUP; // [.., 512, 512] MULTIPLY; // [.., 262144] } void make_jump19() { DUP; // [.., 2, 2] make_jump18(); // [.., 2, 262144] MULTIPLY; // [.., 524288] } void print_stack() { if (VERBOSE) { for (int i = 0; i <= si; ++i) { std::cout << S[i] << ' '; } std::cout << '\n'; } } // Enter with [2, L] // - go to jmp with [L, 2] // - retain=false: [L, jmp] // - retain=true: [2, L, jmp] void jump(int j, bool retain) { if (retain) { OVER; // [2, L, 2] } else { SWAP; // [L, 2] } switch(j) { case 2: { make_jump2(); break; } case 3: { make_jump3(); break; } case 4: { make_jump4(); break; } case 5: { make_jump5(); break; } case 6: { make_jump6(); break; } case 7: { make_jump7(); break; } case 8: { make_jump8(); break; } case 9: { make_jump9(); break; } case 10: { make_jump10(); break; } case 11: { make_jump11(); break; } case 12: { make_jump12(); break; } case 13: { make_jump13(); break; } case 14: { make_jump14(); break; } case 15: { make_jump15(); break; } case 16: { make_jump16(); break; } case 17: { make_jump17(); break; } case 18: { make_jump18(); break; } case 19: { make_jump19(); break; } default: break; } } struct Number { uint64_t x; uint64_t L; std::vector jumps; Number(uint64_t x_) { x = x_; L = MSBL(x_); std::vector ones; for (uint64_t b = 4, i = 2; b <= L; b <<= 1, ++i) { if (x & b) ones.push_back(i); } int i = 1; for (auto o : ones) { jumps.push_back(o - i); i = o; } } }; #define PREV3(OP1_, OP2_, OP3_) (OP[i - 2] == OP1_ && OP[i - 1] == OP2_ && OP[i] == OP3_) #define PREV5(OP1_, OP2_, OP3_, OP4_, OP5_) (OP[i - 4] == OP1_ && OP[i - 3] == OP2_ && PREV3(OP3_, OP4_, OP5_)) #define POP(cnt_) int cnt__ = cnt_; do { OP_new.pop_back(); } while (cnt__--) bool fix() { bool fixed = false; std::vector OP_new = {OP[0], OP[1]}; auto sz = OP.size(); for (std::size_t i = 2; i < sz; ++i) { OP_new.push_back(OP[i]); // SWAP OVER SWAP => DUP OVER if (PREV3("SWAP", "OVER", "SWAP")) { POP(3); OP_new.push_back("DUP"); OP_new.push_back("OVER"); fixed = true; } // DUP SWAP OVER => DUP DUP if (PREV3("DUP", "SWAP", "OVER")) { POP(2); OP_new.push_back("DUP"); fixed = true; } // OVER OVER DUP * * => DUP * OVER * if (i >= 4 && PREV5("OVER", "OVER", "DUP", "*", "*")) { POP(5); OP_new.push_back("DUP"); OP_new.push_back("*"); OP_new.push_back("OVER"); OP_new.push_back("*"); } } OP = OP_new; return fixed; } // Stack assumption when building normally: // - [2, L], where L is current 1 << b int main() { int t; std::cin >> t; for (int i = 0; i < t; ++i) { si = 0; S[0] = 1; OP.clear(); uint64_t x; std::cin >> x; assert(x >= 4); if (VERBOSE) std::cout << "Solving: " << x << '\n'; Number n(x); if (VERBOSE) { for (auto i = 1, bi = 1; i < 20; ++i, bi <<= 1) { std::cout << ((x & bi) ? 1 : 0); } std::cout << '\n'; std::cout << "JUMPS:"; for (const auto jmp : n.jumps) std::cout << " " << jmp; std::cout << '\n'; } if (x & 1) { DUP; // [1, 1] } DUP; // [1, 1, 1] or [1, 1] PLUS; // [1, 2] or [2] DUP; // [1, 2, 2] or [2, 2] print_stack(); for (std::size_t j = 0; j < n.jumps.size(); ++j) { auto jmp = n.jumps[j]; // Keep current one: if (j > 0 || (x & 2)) { SWAP; // [.., L, 2] OVER; // [.., L, 2, L] } const auto retain = j != n.jumps.size() - 1; if (jmp == 1) { if (retain) { OVER; // [.., L, 2, L, 2]; } MULTIPLY; // [.., L, 2?, L * 2] } else { jump(jmp, retain); // [L, 2?, L, jmp] MULTIPLY; // [L, 2?, L * jmp] } print_stack(); } while (si > 0) { PLUS; print_stack(); } assert(si == 0); assert(S[0] == x); while (fix()) { }; std::cout << OP.size() << '\n'; for (const auto& op : OP) { std::cout << op << ' '; } std::cout << '\n'; } }