// Ladder construction: try to get T > 2^(d+1)-1 with d POPs // by using non-standard push chars that create cross-references. // // Consider d=26 (n=27). Standard chain max T = 2^27-1 = 134M. // We need T = 150M. // // What if POP j pushes char (j+1) [standard] but goes to a deeper goto? // In the standard chain, solve(j, x) for x != j+1: // cost = 1 + solve(gy[j], j+1).steps + solve(j+1, x).steps // where solve(gy[j], j+1) traverses from gy[j] to j (cost depends on gy[j]) // and solve(j+1, x) continues the chain. // // With gy[j]=0 for all j: solve(j, x) = 2^(j+1) * solve_x_factor + stuff // Each level doubles. // // What if some instruction pushes a char that causes the resolve step // to call MULTIPLE pops? E.g., if POP 5 pushes char 3 instead of char 6, // then solve(gy[5], 3) goes to gy[5], and char 3 gets popped by POP 2 // (which pops char 3). But to reach POP 2 from gy[5], we might traverse // through POPs 0-2, each adding their own costs. // // Wait, that's the same as setting gy[5] to a different value. // Actually no - the push_char determines WHICH POP consumes the push. // In standard chain: push_char = j+1, consumed by POP j itself. // If push_char = 3 (for POP 5), consumed by POP 2. // Then solve(gy[5], 3) returns at POP 2's goto = 3. // Then solve(3, x) continues from POP 3. // But we skipped POPs 3, 4! The resolve step only went to POP 2. // // Actually this makes the resolve step SHORTER, not longer. // To make it LONGER, we want push_char to NOT match any POP's pop_char. // If push_char = d+1 (a char no POP pops), then the char propagates all the way // to HALT. HALT processes it by pushing something else and recursing. // This could create much deeper recursion! // // Let me try: d POP instructions that all pop chars 1..d. // Some POPs push char d+1 (which NO POP pops). // HALT pushes char 1 and goes to some instruction. // When char d+1 reaches HALT, HALT pushes char 1 and continues. // Char 1 gets popped by POP 0, which goes to POP 1. // So the "resolve" for char d+1 goes through the entire chain AND the HALT. #include using namespace std; constexpr long long P = 998244353; // General program: n instructions // Each instruction is POP or HALT with given params // Solve by checker's recursive method struct Program { int n; int type[30]; // 0=POP, 1=HALT int pop_c[30]; // POP char (for POP) int goto1[30]; // goto on pop match (for POP) int push_c[30]; // push char int goto2[30]; // goto on push optional> dp[30][40]; bool vis[30][40]; bool inf; int maxC; void clear_dp() { for (int i = 0; i < n; i++) for (int j = 0; j <= maxC; j++) { dp[i][j].reset(); vis[i][j] = false; } inf = false; } pair solve(int i, int x) { if (dp[i][x]) return dp[i][x].value(); if (vis[i][x]) { inf = true; return {-1, 0}; } vis[i][x] = true; if (type[i] == 0) { if (x == pop_c[i]) { dp[i][x] = {goto1[i], 1LL}; } else { auto [j, u] = solve(goto2[i], push_c[i]); if (inf) return {-1, 0}; auto [k, v] = solve(j, x); if (inf) return {-1, 0}; dp[i][x] = {k, (u + v + 1) % P}; } } else { if (x == 0) { dp[i][x] = {-1, 1LL}; } else { auto [j, u] = solve(goto2[i], push_c[i]); if (inf) return {-1, 0}; auto [k, v] = solve(j, x); if (inf) return {-1, 0}; dp[i][x] = {k, (u + v + 1) % P}; } } return dp[i][x].value(); } long long eval() { clear_dp(); auto [fi, steps] = solve(0, 0); if (inf) return -1; return steps; } }; int main() { long long target1 = 150994941; long long target2 = 150994939; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // Try specific construction: d POP + 1 HALT // POP j: pop char (j+1), goto (j+2) [next POP or HALT] // push char push_c[j], goto push_g[j] // HALT d: push char halt_c, goto halt_g // // Chars used: 1..d for pop_chars, plus additional chars for push. // If push_c[j] > d: no POP pops this char, so it propagates to HALT. // HALT then pushes halt_c and continues. // // This creates a more complex recursion than a simple chain. for (int d = 15; d <= 26; d++) { int n = d + 1; Program prog; prog.n = n; int maxPushChar = d + 3; // allow a few extra chars prog.maxC = maxPushChar; fprintf(stderr, "=== d=%d (n=%d, maxC=%d) ===\n", d, n, maxPushChar); auto dStart = chrono::steady_clock::now(); auto dElapsed = [&]() { return chrono::duration_cast(chrono::steady_clock::now() - dStart).count(); }; bool found = false; for (int restart = 0; dElapsed() < 8000 && !found; restart++) { // Setup structure for (int j = 0; j < d; j++) { prog.type[j] = 0; prog.pop_c[j] = j + 1; prog.goto1[j] = j + 1; // standard: next instruction prog.push_c[j] = 1 + rng() % maxPushChar; prog.goto2[j] = rng() % n; } prog.type[d] = 1; prog.push_c[d] = 1 + rng() % maxPushChar; prog.goto2[d] = rng() % n; long long T = prog.eval(); if (T < 0) continue; for (int iter = 0; iter < 300000 && !found; iter++) { if (T == target1 || T == target2) { found = true; fprintf(stderr, "FOUND! d=%d n=%d T=%lld\n", d, n, T); printf("%d\n", n); for (int j = 0; j < d; j++) { printf("POP %d GOTO %d PUSH %d GOTO %d\n", prog.pop_c[j], prog.goto1[j]+1, prog.push_c[j], prog.goto2[j]+1); } printf("HALT PUSH %d GOTO %d\n", prog.push_c[d], prog.goto2[d]+1); break; } // Mutate int j = rng() % n; int what = rng() % 3; int sv_push = prog.push_c[j], sv_g2 = prog.goto2[j], sv_g1 = prog.goto1[j]; if (what == 0) prog.push_c[j] = 1 + rng() % maxPushChar; else if (what == 1) prog.goto2[j] = rng() % n; else if (j < d) prog.goto1[j] = rng() % n; // vary pop goto too long long nT = prog.eval(); if (nT < 0) { prog.push_c[j] = sv_push; prog.goto2[j] = sv_g2; prog.goto1[j] = sv_g1; continue; } long long nd1 = min((nT - target1 + P) % P, (target1 - nT + P) % P); long long od1 = min((T - target1 + P) % P, (target1 - T + P) % P); long long nd2 = min((nT - target2 + P) % P, (target2 - nT + P) % P); long long od2 = min((T - target2 + P) % P, (target2 - T + P) % P); long long best_nd = min(nd1, nd2); long long best_od = min(od1, od2); if (best_nd <= best_od) T = nT; else { prog.push_c[j] = sv_push; prog.goto2[j] = sv_g2; prog.goto1[j] = sv_g1; } } if (restart % 200 == 0 && restart > 0) fprintf(stderr, "d=%d restart=%d elapsed=%ldms\n", d, restart, dElapsed()); } if (found) return 0; } return 0; }