#include "prison.h" #include <vector> #include <bits/stdc++.h> using namespace std; vector<vector<int>> devise_strategy(int n) { int s = (int)sqrt(n) + 1; int x = 3 * s; vector<vector<int>> ans(x + 1, vector<int>(n + 1, 0)); ans[0][0] = 0; for (int a = 1; a <= n; a++) ans[0][a] = (int)sqrt(a); for (int k = 1; k < s; k++) { ans[k][0] = 1; for (int b = 1; b <= n; b++) { int kb = (int)sqrt(b); if (kb == k) ans[k][b] = s; else ans[k][b] = (k < kb) ? -1 : -2; } } ans[s][0] = 0; for (int a = 1; a <= n; a++) { int k = (int)sqrt(a); int sq = k * k; int r = a - sq; ans[s][a] = s + 1 + r; } for (int st = s + 1; st <= x; st++) { ans[st][0] = 1; int ra = st - s - 1; for (int b = 1; b <= n; b++) { int k = (int)sqrt(b); int sq = k * k; int rb = b - sq; ans[st][b] = (rb < ra) ? -2 : -1; } } return ans; }