#include "prison.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int CHECK_A = 0, CHECK_B = 1, DECLARE_A_LESS = -1, DECLARE_B_LESS = -2;
int layers(int N) {
if (N < 3) return 1;
else return 1 + layers(N / 3);
}
int getNthLSD(int N, int i) {
if (i == 0) return N % 3;
else return getNthLSD(N/3, i-1);
}
std::vector<std::vector<int>> devise_strategy(int N) {
// we need 3 log3(N) + 1 states
int L = layers(N-1);
vector<vector<int>> ans(3 * layers(N-1) + 1, vector<int>(N+1));
// 0 move to {1, 2, 3} depending on A's L-1th ternary digit
ans[0][0] = CHECK_A;
for (int aval = 1; aval <= N; ++aval) ans[0][aval] = getNthLSD(aval-1, L-1) + 1;
for (int layer = 1; 3 * layer <= ans.size(); ++layer) {
// if odd layer, A's digit is written
// if even layer, B's digit is written
for (int state = 3 * layer - 2; state < 3 * layer; ++state) {
ans[state][0] = (layer % 2 == 1 ? CHECK_B : CHECK_A); // check opposite number
int storedDigit = (state - 1) % 3;
for (int oval = 1; oval <= N; ++oval) { // other value
int otherDigit = getNthLSD(oval-1, L-layer);
if (storedDigit != otherDigit) {
int storedLessOtherAns = DECLARE_A_LESS, storedGreaterOtherAns = DECLARE_B_LESS;
// if it's actually B that's stored, interchange the two
if (layer % 2 == 0) swap(storedLessOtherAns, storedGreaterOtherAns);
if (storedDigit > otherDigit) ans[state][oval] = storedGreaterOtherAns;
else ans[state][oval] = storedLessOtherAns;
} else { // store the next digit and move states
// the two numbers are equal. this shouldn't happen
if (3 * layer + 1 == ans.size()) {
ans[state][oval] = 0;
} else {
int digitToStore = getNthLSD(oval-1, L-layer-1);
ans[state][oval] = digitToStore + 1 + 3 * layer;
}
}
}
}
}
return ans;
}
Compilation message
towers.cpp:1:10: fatal error: prison.h: No such file or directory
1 | #include "prison.h"
| ^~~~~~~~~~
compilation terminated.
