#include "prison.h"
#include <vector>
#include <cstdio>
using namespace std;
// <|°_°|>
// M. Broccoli
// The hardest choices require the strongest wills
// What is better - to be born good, or to overcome your evil nature with great effort ?
const int SIZE = (20);
const int MAXIMUM = (5001);
int Answer[SIZE + 1][MAXIMUM];
int done = 0;
int IsSmaller(int bag) {
return bag ? -2 : -1;
}
void Fill(int number, int left, int right) {
int rest = 0, cut = 3, bag = 0;
if (number > 5)
bag = (number / 3) & 1, rest = number % 3;
else if (number > 1)
bag = (number >> 2) & 1, rest = number & 1, cut = 2;
else
bag = 1, cut = 1;
Answer[number][0] = bag;
Answer[number][left ++] = IsSmaller(bag);
Answer[number][-- right] = IsSmaller(!bag);
if (!number)
left --, right ++;
int mini = left + ((right - left) * rest + cut - 1) / cut;
int maxi = left + ((right - left) * (rest + 1) + cut - 1) / cut;
for (int i = left; i <= mini; i ++)
{
Answer[number][i] = IsSmaller(bag);
}
for (int i = maxi - 1; i < right; i ++)
{
Answer[number][i] = IsSmaller(!bag);
}
int nv = number ? number - rest : 21;
if (number == 1)
return;
if (!number)
cut = 3;
if (number == 2 || number == 3)
cut = 1;
if (number / 3 == 2)
cut = 2;
nv -= cut;
mini ++, maxi --;
for (int i = mini; i < maxi; i ++)
{
Answer[number][i] = nv + (i - mini) * cut / (maxi - mini);
}
for (int i = 0; i < cut; i ++)
{
Fill(nv + i, mini - 1, maxi + 1);
}
return;
}
vector <vector <int>> devise_strategy(int maximum) {
if (!done)
Fill(0, 1, MAXIMUM), done = 1;
vector <vector <int>> ans(SIZE + 1);
for (int i = 0; i <= SIZE; i ++)
{
ans[i].resize(maximum + 1, 0);
for (int j = 0; j <= maximum; j ++)
ans[i][j] = Answer[i][j];
}
return ans;
}
