#include using namespace std; typedef uint64_t pino_key_t; union pino_key_union_t { pino_key_t key; struct { pino_key_t pino_tulo_1 : 16, pino_tulo_2 : 16, pino_summa : 16, a : 8, b : 8; }; }; constexpr int PINOJA = 3; unordered_map pinot[PINOJA]; unordered_map> ohjelmat; int pino_[64] = {0, 0, 1}; int* const pino = &pino_[2]; int pino_summa = 1; int pino_i = 0; constexpr int pino_max = 8; const char* komennot_[64] = {0}; const char** komennot = &komennot_[2]; constexpr int komennot_max = 20; constexpr long tulos_max = 1000000; const char *PLUS = "+ ", *MUL = "* ", *DUP = "DUP ", *DROP = "DROP ", *SWAP = "SWAP ", *OVER = "OVER ", *ROT = "ROT "; void tulosta(int tulos, int pituus, string ohjelma) { ifstream f("3d.best." + to_string(tulos)); int vanha_pituus; if (!(f >> vanha_pituus) || vanha_pituus > pituus) { ofstream f2("3d.best." + to_string(tulos)); f2 << pituus << "\n" << ohjelma << "\n"; cout << tulos << "\t" << pituus << "\t" << ohjelma << "\n"; } } constexpr int primes_16[] = {65521, 65519, 65497, 65479, 65449, 65447, 65437, 65423, 65419, 65413, 65407, 65393, 65381, 65371, 65357, 65353}; constexpr int primes_8[] = {251, 241, 239, 233, 229, 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167}; void dfs(int k) { if (k + pino_i > komennot_max) { return; } pino_key_union_t pino_key = {0}; pino_key.pino_summa = pino_summa % primes_16[0]; uint64_t pino_tulo_1 = 1, pino_tulo_2 = 1; for (int i = 0; i <= pino_i; i++) { pino_tulo_1 *= pino[i]; pino_tulo_1 %= primes_16[1]; pino_tulo_2 *= pino[i]; pino_tulo_2 %= primes_16[2]; } pino_key.pino_tulo_1 = pino_tulo_1; pino_key.pino_tulo_2 = pino_tulo_2; pino_key.a = pino[pino_i] % primes_8[0]; pino_key.b = pino[pino_i-1] % primes_8[1]; if (pinot[0].count(pino_key.key) && pinot[0][pino_key.key] <= k + pino_i) { return; } pinot[0][pino_key.key] = k + pino_i; if (pinot[0].size() > 20000000 / PINOJA) { swap(pinot[1], pinot[2]); swap(pinot[0], pinot[1]); pinot[0].clear(); } for (int i = 1; i < PINOJA; i++) { if (pinot[i].count(pino_key.key) && pinot[i][pino_key.key] <= k + pino_i) { return; } } if (ohjelmat.count(pino_summa) && k + pino_i < ohjelmat[pino_summa].first) { string ohjelma; for (int i = 0; i < k; i++) { ohjelma += komennot[i]; } for (int i = 0; i < pino_i; i++) { ohjelma += PLUS; } ohjelma.resize(ohjelma.size() - 1); ohjelmat[pino_summa] = {k + pino_i, ohjelma}; tulosta(pino_summa, k + pino_i, ohjelma); } int &a = pino[pino_i], &b = pino[pino_i-1], &c = pino[pino_i-2]; int vanha_summa = pino_summa; int vanhat[3] = {a, b, c}; int vanha_i = pino_i; auto palauta = [&]() { pino_summa = vanha_summa; pino_i = vanha_i; a = vanhat[0]; b = vanhat[1]; c = vanhat[2]; }; // + auto do_PLUS = [&]() { if (b && a + b <= tulos_max) { b = a + b; pino_i--; komennot[k] = PLUS; dfs(k + 1); palauta(); } }; // * auto do_MUL = [&]() { if (b && (long)a * b <= tulos_max) { pino_summa -= a + b; b = a * b; pino_i--; pino_summa += b; komennot[k] = MUL; dfs(k + 1); palauta(); } }; // ROT auto do_ROT = [&]() { if (c && (komennot[k-1] != ROT || komennot[k-2] != ROT)) { int tmp = c; c = b; b = a; a = tmp; komennot[k] = ROT; dfs(k + 1); palauta(); } }; // SWAP auto do_SWAP = [&]() { if (b && komennot[k-1] != SWAP) { swap(a, b); komennot[k] = SWAP; dfs(k + 1); palauta(); } }; // DUP auto do_DUP = [&]() { if (pino_i < pino_max) { pino_i++; pino[pino_i] = a; pino_summa += a; komennot[k] = DUP; dfs(k + 1); palauta(); } }; // OVER auto do_OVER = [&]() { if (b && pino_i < pino_max) { pino_i++; pino[pino_i] = b; pino_summa += b; komennot[k] = OVER; dfs(k + 1); palauta(); } }; do_PLUS(); do_MUL(); do_OVER(); do_SWAP(); do_ROT(); do_DUP(); } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int j; cin >> j; ohjelmat[j] = {komennot_max + 1, ""}; } dfs(0); }