File size: 4,560 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 | #include <bits/stdc++.h>
using namespace std;
static const long long P = 998244353;
long long Sv[35];
inline long long computeT(int d, const int* gy) {
Sv[0] = 0;
for (int j = 0; j < d; j++) {
long long c = ((Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P + P) % P;
Sv[j + 1] = (Sv[j] + c) % P;
}
return (Sv[d] + d + 1) % P;
}
int main(int argc, char** argv) {
long long target;
int minD = 20, maxD = 27;
if (argc >= 2) target = atoll(argv[1]);
else target = 150994941LL; // default: target1
if (argc >= 3) minD = atoi(argv[2]);
if (argc >= 4) maxD = atoi(argv[3]);
cerr << "Target: " << target << " searching d=" << minD << ".." << maxD << endl;
mt19937 rng(target * 1000003ULL + 42);
for (int d = minD; d <= maxD; d++) {
cerr << "Trying d=" << d << " (n=" << (d+1) << ")" << endl;
auto startTime = chrono::steady_clock::now();
int timeLimit = 30000; // 30s per d
int gy[35];
int bestGy[35];
bool found = false;
long long attempts = 0;
while (!found) {
auto now = chrono::steady_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
if (ms > timeLimit) break;
// Random restart
gy[0] = 0;
for (int j = 1; j < d; j++) gy[j] = rng() % (j + 1);
long long T = computeT(d, gy);
if (T == target) { found = true; memcpy(bestGy, gy, sizeof(int)*d); break; }
// Aggressive hill climbing with restarts
long long bestDist = min((T - target + P) % P, (target - T + P) % P);
int noImprove = 0;
for (int iter = 0; iter < 200000 && !found; iter++) {
// Try modifying 1 or 2 positions
int nmod = (rng() % 4 == 0) ? 2 : 1;
int saved_j[2], saved_g[2];
for (int m = 0; m < nmod; m++) {
int j = 1 + rng() % (d - 1);
saved_j[m] = j;
saved_g[m] = gy[j];
gy[j] = rng() % (j + 1);
}
long long nT = computeT(d, gy);
if (nT == target) {
found = true;
memcpy(bestGy, gy, sizeof(int)*d);
break;
}
long long nd = min((nT - target + P) % P, (target - nT + P) % P);
if (nd < bestDist) {
T = nT;
bestDist = nd;
noImprove = 0;
} else if (nd == bestDist && (rng() % 2 == 0)) {
// Accept sideways move with 50% probability
T = nT;
noImprove++;
} else {
// Revert
for (int m = nmod - 1; m >= 0; m--) {
gy[saved_j[m]] = saved_g[m];
}
noImprove++;
}
// If stuck, do a bigger perturbation
if (noImprove > 500) {
int nflip = 2 + rng() % (d / 3);
for (int f = 0; f < nflip; f++) {
int j = 1 + rng() % (d - 1);
gy[j] = rng() % (j + 1);
}
T = computeT(d, gy);
bestDist = min((T - target + P) % P, (target - T + P) % P);
if (T == target) { found = true; memcpy(bestGy, gy, sizeof(int)*d); }
noImprove = 0;
}
attempts++;
}
}
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
cerr << " attempts=" << attempts << " time=" << ms << "ms found=" << found << endl;
if (found) {
cout << "FOUND d=" << d << " gy:";
for (int j = 0; j < d; j++) cout << " " << bestGy[j];
cout << endl;
// Verify
long long T = computeT(d, bestGy);
cout << "T=" << T << " target=" << target << " match=" << (T == target) << endl;
// Output program
cout << (d+1) << endl;
for (int j = 0; j < d; j++) {
cout << "POP " << (j+1) << " GOTO " << (j+2)
<< " PUSH " << (j+1) << " GOTO " << (bestGy[j]+1) << endl;
}
cout << "HALT PUSH 1 GOTO " << (d+1) << endl;
break;
}
}
return 0;
}
|