#include "prison.h"
#include <iostream>
using namespace std;
int solve(int a, int b)
{
const int MAXN = 5102;
int l=1; int r = MAXN;
int t = (((a+2)/3) % 2 ? 1: 0);
for(int i=0; i<(a-1)/3; i++)
{
int t1 = (2*(l+1) + r)/3;
int t2 = ((l+1) + 2*r)/3;
if(l < b && b < t1)
{
l = l+1;
r = t1-1;
}
else if(t1 <= b && b < t2)
{
l = t1; r = t2-1;
}
else if(t2 <= b && b < r)
{
l = t2; r = r-1;
}
else if(b == l)
{
return -1;
}
else if(b == r)
{
return -1;
}
}
if(1 <= a && a <= 18)
{
int t1 = (2*(l+1) + r)/3;
int t2 = ((l+1) + 2*r)/3;
if(a % 3 == 1)
{
l = l+1; r = t1-1;
}
if(a % 3 == 2)
{
l = t1; r = t2-1;
}
if(a % 3 == 0)
{
l = t2; r = r-1;
}
}
if(a == 19)
{
l = l+1; r = l+1;
}
if(a == 20)
{
l = l+3; r = l+1;
}
if(b <= l)
{
return -1-t;
}
if(b >= r)
{
return t-2;
}
int cur = (a+2)/3 * 3;
if(a <= 15)
{
int t1 = (2*(l+1) + r)/3;
int t2 = ((l+1) + 2*r)/3;
if(l < b && b < t1)
{
return cur+1;
}
else if(t1 <= b && b < t2)
{
return cur+2;
}
else if(t2 <= b && b < r)
{
return cur+3;
}
}
else
{
if(b <= l+2)
{
return cur+1;
}
else
{
return cur+2;
}
}
return 0;
}
vector<vector<int> > devise_strategy(int N)
{
const int x = 20;
vector<vector<int> > strategy(x+1, vector<int>(N+1));
for(int i=0; i<=x; i++)
{
strategy[i][0] = (((i+2)/3) % 2 ? 1: 0);
for(int j=1; j<=N; j++)
{
strategy[i][j] = solve(i, j);
}
}
return strategy;
}
