| |
| P = 998244353 |
|
|
| def evaluate(n, instructions): |
| dp = {} |
| vis = set() |
|
|
| def solve(i, x): |
| if (i, x) in dp: return dp[(i, x)] |
| if (i, x) in vis: return None |
| vis.add((i, x)) |
|
|
| inst = instructions[i] |
| if inst[0] == 'POP': |
| _, pop_c, g1, push_c, g2 = inst |
| if x == pop_c: |
| dp[(i, x)] = (g1, 1) |
| else: |
| r = solve(g2, push_c) |
| if r is None: return None |
| j, u = r |
| r2 = solve(j, x) |
| if r2 is None: return None |
| k, v = r2 |
| dp[(i, x)] = (k, (u + v + 1) % P) |
| else: |
| _, push_c, g2 = inst |
| if x == 0: |
| dp[(i, x)] = (-1, 1) |
| else: |
| r = solve(g2, push_c) |
| if r is None: return None |
| j, u = r |
| r2 = solve(j, x) |
| if r2 is None: return None |
| k, v = r2 |
| dp[(i, x)] = (k, (u + v + 1) % P) |
|
|
| return dp[(i, x)] |
|
|
| r = solve(0, 0) |
| if r is None: return -1 |
| return r[1] |
|
|
| |
| |
|
|
| best_T = 0 |
| best_prog = None |
|
|
| |
| n = 4 |
| A = 6 |
|
|
| import itertools |
| count = 0 |
| for i0_pop in range(1, A+1): |
| for i0_g1 in range(n): |
| for i0_push in range(1, A+1): |
| for i0_g2 in range(n): |
| for i1_pop in range(1, A+1): |
| for i1_g1 in range(n): |
| for i1_push in range(1, A+1): |
| for i1_g2 in range(n): |
| for i2_pop in range(1, A+1): |
| for i2_g1 in range(n): |
| for i2_push in range(1, A+1): |
| for i2_g2 in range(n): |
| for h_push in range(1, A+1): |
| for h_g2 in range(n): |
| instrs = [ |
| ('POP', i0_pop, i0_g1, i0_push, i0_g2), |
| ('POP', i1_pop, i1_g1, i1_push, i1_g2), |
| ('POP', i2_pop, i2_g1, i2_push, i2_g2), |
| ('HALT', h_push, h_g2), |
| ] |
| T = evaluate(n, instrs) |
| count += 1 |
| if T > 0 and T > best_T: |
| best_T = T |
| best_prog = instrs |
| if T > 100: |
| print(f"New best T={T}: {instrs}") |
| if count % 10000000 == 0: |
| print(f" {count} configs tested, best T={best_T}") |
|
|
| print(f"\nTotal: {count} configs. Best T = {best_T}") |
| print(f"Best prog: {best_prog}") |
|
|
