File size: 7,341 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 | // Analyze what step counts are achievable with small n and varying alphabet
// Try to understand the structure of possible step counts
#include <bits/stdc++.h>
using namespace std;
constexpr long long P = 998244353;
struct MInt {
long long x;
MInt(): x(0) {}
MInt(long long v): x(((v % P) + P) % P) {}
MInt operator+(const MInt& b) const { return MInt(x + b.x); }
MInt operator-(const MInt& b) const { return MInt(x - b.x); }
MInt operator*(const MInt& b) const { return MInt(x * b.x); }
bool operator==(const MInt& b) const { return x == b.x; }
};
int n_instr;
int type_arr[30]; // 0=POP, 1=HALT
int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];
int maxChar;
optional<pair<int, MInt>> dp[30][1030];
bool vis[30][1030];
bool infinite_flag;
pair<int, MInt> solve(int i, int x) {
if (dp[i][x]) return dp[i][x].value();
if (vis[i][x]) { infinite_flag = true; return {-1, MInt(0)}; }
vis[i][x] = true;
if (type_arr[i] == 0) { // POP
if (x == pop_char_arr[i]) {
dp[i][x] = {goto1_arr[i], MInt(1)};
} else {
auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
if (infinite_flag) return {-1, MInt(0)};
auto [k, v] = solve(j, x);
if (infinite_flag) return {-1, MInt(0)};
dp[i][x] = {k, u + v + MInt(1)};
}
} else { // HALT
if (x == 0) {
dp[i][x] = {-1, MInt(1)};
} else {
auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
if (infinite_flag) return {-1, MInt(0)};
auto [k, v] = solve(j, x);
if (infinite_flag) return {-1, MInt(0)};
dp[i][x] = {k, u + v + MInt(1)};
}
}
return dp[i][x].value();
}
MInt evaluate() {
for (int i = 0; i < n_instr; i++)
for (int j = 0; j <= maxChar; j++) {
dp[i][j].reset();
vis[i][j] = false;
}
infinite_flag = false;
auto [fi, steps] = solve(0, 0);
if (infinite_flag) return MInt(P - 1); // sentinel for infinite
return steps;
}
int main() {
// Let's try a specific structure:
// n=2: one HALT + one POP
// HALT pushes some char b and goes to instruction g
// POP pops some char a, goto g1, push char c, goto g2
// With n=2, alphabet {1..A}:
// Instruction 0: HALT PUSH b GOTO g (g in {0,1})
// Instruction 1: POP a GOTO g1 PUSH c GOTO g2
// solve(0, 0) = 1 (halt immediately)
// solve(0, x) for x != 0: push b, goto g. So solve(g, b) then solve(result, x)
// steps = 1 + solve(g, b).steps + solve(solve(g,b).ret, x).steps
// Let's manually compute for n=2:
// Instr 0: HALT PUSH 1 GOTO 1
// Instr 1: POP 1 GOTO 0 PUSH 1 GOTO 0
//
// solve(0, 0) = (-1, 1) -- halt
// solve(1, 1) = (0, 1) -- pop, goto 0
// solve(0, x) for x>0: push 1 goto 1. solve(1, 1) = (0, 1). solve(0, x).
// But this is circular! solve(0, x) depends on solve(0, x).
// So this program doesn't halt for x > 0 (other than when x is on the HALT path)
// For the program to halt, we need no cycles in the dependency graph.
// With n=2, alphabet 1..2:
// Instr 0: HALT PUSH 1 GOTO 1
// Instr 1: POP 2 GOTO 0 PUSH 1 GOTO 0
//
// solve(0, 0) = (-1, 1)
// solve(1, 2) = (0, 1) -- pop, goto 0
// solve(0, x) for x != 0: push 1, goto 1, solve(1, 1)
// solve(1, 1): x=1 != 2 (pop char). Push 1, goto 0. solve(0, 1) then solve(result, 1).
// solve(0, 1): push 1, goto 1. solve(1, 1) -- CYCLE! infinite.
// Hmm. The challenge with small n is avoiding cycles.
// Chain programs avoid cycles by having strictly increasing instruction indices.
// Let me think about what makes chain programs special:
// Chain: instrs 0..d-1 are POP, instr d is HALT
// POP j: pops char (j+1), goto (j+1), push char (j+1), goto gy[j]
// HALT d: push 1, goto d
// The key is: POP j pops char (j+1). So when we push char (j+1) and call solve(gy[j], j+1),
// the only instruction that can pop char (j+1) is instruction j itself.
// This creates a well-structured recursion.
// For non-chain: we could use different characters to create multiple "levels" of recursion
// with the same instruction. E.g., one POP instruction that handles multiple stack symbols.
// Actually, let me think about n=3 with the right structure:
// If we can get 2 POP instructions to both create exponential growth,
// and chain them, we might get 2^a * 2^b type behavior with a+b controlled.
// Actually, let me try a different approach: enumerate step counts for very small programs
n_instr = 3;
maxChar = 4;
set<long long> seen_steps;
long long max_steps = 0;
// Enumerate all programs with n=3, alphabet 1..4
// Last instruction must be HALT
// Try all configurations
int count = 0;
int halting = 0;
for (int t0 = 0; t0 <= 1; t0++)
for (int t1 = 0; t1 <= 1; t1++) {
type_arr[2] = 1; // HALT
type_arr[0] = t0;
type_arr[1] = t1;
auto enumerate_instr = [&](int i, auto& self, auto& callback) -> void {
if (i == n_instr) {
callback();
return;
}
if (type_arr[i] == 0) { // POP
for (int a = 1; a <= maxChar; a++)
for (int g1 = 0; g1 < n_instr; g1++)
for (int c = 1; c <= maxChar; c++)
for (int g2 = 0; g2 < n_instr; g2++) {
pop_char_arr[i] = a;
goto1_arr[i] = g1;
push_char_arr[i] = c;
goto2_arr[i] = g2;
self(i + 1, self, callback);
}
} else { // HALT
for (int c = 1; c <= maxChar; c++)
for (int g2 = 0; g2 < n_instr; g2++) {
push_char_arr[i] = c;
goto2_arr[i] = g2;
self(i + 1, self, callback);
}
}
};
auto callback = [&]() {
count++;
MInt T = evaluate();
if (T.x != (P - 1) % P) {
halting++;
seen_steps.insert(T.x);
if (T.x > max_steps) {
max_steps = T.x;
cerr << "New max: " << T.x << " with config:";
for (int i = 0; i < n_instr; i++) {
if (type_arr[i] == 0) {
cerr << " POP" << pop_char_arr[i] << "→" << goto1_arr[i] << ",push" << push_char_arr[i] << "→" << goto2_arr[i];
} else {
cerr << " HALT,push" << push_char_arr[i] << "→" << goto2_arr[i];
}
}
cerr << endl;
}
}
};
enumerate_instr(0, enumerate_instr, callback);
}
cout << "Total programs: " << count << ", halting: " << halting << endl;
cout << "Distinct step counts: " << seen_steps.size() << endl;
cout << "Max step count: " << max_steps << endl;
cout << "First 50 step counts:";
int printed = 0;
for (long long v : seen_steps) {
if (printed++ >= 50) break;
cout << " " << v;
}
cout << endl;
return 0;
}
|