#include "prison.h"
#include <vector>
#include <iostream>
using namespace std;
pair<int, int> split_range(int value, int a, int b) {
// Remove endpoints
a++;
b--;
int dif = b - a;
dif /= 2;
int c = a + dif;
if (value <= c) return {a, c};
return {c + 1, b};
}
pair<int, int> find_range(int value, int steps) {
int a = 1;
int b = 5000;
while (steps--) {
auto p = split_range(value, a, b);
a = p.first;
b = p.second;
}
return {a, b};
}
int ans(bool low, bool t) {
if (!low) t = !t;
// B A
return t ? -2 : -1;
}
int handle(int i, int j) {
// 0 -> 0
// 1/2 -> 1
// 3/4 -> 2
int steps = (i + 1) / 2;
bool t = steps % 2;
//cout << i << " j: " << j << " steps: " << steps << " turn: " << (t ? "B" : "A") << endl;
if (j == 0) return t;
auto r = find_range(j, steps);
if (r.first >= j) {
return ans(1, t);
} else if (r.second <= j) {
return ans(0, t);
}
auto nr = split_range(j, r.first, r.second);
if (nr.first == r.first + 1) {
return steps * 2 + 1;
} else {
return steps * 2 + 2;
}
}
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> res;
int mx = 50;
for (int i = 0; i <= mx; ++i) {
vector<int> cur;
for (int j = 0; j <= N; ++j) {
cur.push_back(min(handle(i, j), mx));
}
res.push_back(cur);
}
/*for (auto g : res) {
for (int x : g) cout << x << " ";
cout << endl;
}*/
return res;
}
