| |
| #include <bits/stdc++.h> |
| using namespace std; |
|
|
| constexpr long long P = 998244353; |
|
|
| int n_instr = 4; |
| int maxChar = 3; |
| int type_arr[30]; |
| int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30]; |
|
|
| optional<pair<int, long long>> dp[30][10]; |
| bool vis[30][10]; |
| bool infinite_flag; |
|
|
| pair<int, long long> solve(int i, int x) { |
| if (dp[i][x]) return dp[i][x].value(); |
| if (vis[i][x]) { infinite_flag = true; return {-1, 0}; } |
| vis[i][x] = true; |
|
|
| if (type_arr[i] == 0) { |
| if (x == pop_char_arr[i]) { |
| dp[i][x] = {goto1_arr[i], 1LL}; |
| } else { |
| auto [j, u] = solve(goto2_arr[i], push_char_arr[i]); |
| if (infinite_flag) return {-1, 0}; |
| auto [k, v] = solve(j, x); |
| if (infinite_flag) 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_arr[i], push_char_arr[i]); |
| if (infinite_flag) return {-1, 0}; |
| auto [k, v] = solve(j, x); |
| if (infinite_flag) return {-1, 0}; |
| dp[i][x] = {k, (u + v + 1) % P}; |
| } |
| } |
| return dp[i][x].value(); |
| } |
|
|
| long long 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 -1; |
| return steps; |
| } |
|
|
| int main() { |
| long long max_steps = 0; |
| int halting = 0; |
| set<long long> seen; |
|
|
| |
| mt19937 rng(42); |
| for (int trial = 0; trial < 10000000; trial++) { |
| |
| for (int i = 0; i < n_instr; i++) { |
| if (i == n_instr - 1) { |
| type_arr[i] = 1; |
| } else { |
| type_arr[i] = (rng() % 3 == 0) ? 1 : 0; |
| } |
| if (type_arr[i] == 0) { |
| pop_char_arr[i] = 1 + rng() % maxChar; |
| goto1_arr[i] = rng() % n_instr; |
| push_char_arr[i] = 1 + rng() % maxChar; |
| goto2_arr[i] = rng() % n_instr; |
| } else { |
| push_char_arr[i] = 1 + rng() % maxChar; |
| goto2_arr[i] = rng() % n_instr; |
| } |
| } |
|
|
| long long T = evaluate(); |
| if (T >= 0) { |
| halting++; |
| seen.insert(T); |
| if (T > max_steps) { |
| max_steps = T; |
| fprintf(stderr, "New max: %lld at trial %d\n", T, trial); |
| } |
| } |
| } |
|
|
| printf("Halting: %d, distinct: %zu, max: %lld\n", halting, seen.size(), max_steps); |
| |
| vector<long long> vals(seen.begin(), seen.end()); |
| sort(vals.rbegin(), vals.rend()); |
| printf("Top 20:"); |
| for (int i = 0; i < min(20, (int)vals.size()); i++) printf(" %lld", vals[i]); |
| printf("\n"); |
|
|
| return 0; |
| } |
|
|
