#include "prison.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
vector<vector<int> > s;
int fewer(int bag)
{
return -1-bag;
}
int child(int num,int ind)
{
if(num>0)
{
if(num%3==0) num-=3;
num=num+3-(num%3);
}
return num+ind;
}
void write(int num,int coins,int newNum)
{
if(newNum>20) return;
s[num][coins]=newNum;
}
void rec(int num,int bag,int l,int r,int parl,int parr)
{
if(num>20) return;
if(l>r) return;
if(l>=r-1)
{
for(int i=parl;i<=parr;i++)
{
if(i<=l) write(num,i,fewer(bag));
else if(r<=i) write(num,i,fewer(bag^1));
}
return;
}
int d=r-1-l;
int len1,len2,len3;
if(d<=4)
{
len1=len2=d/2;
if(d%2>0) len1++;
}
else
{
len1=len2=len3=d/3;
if(d%3>0) len1++;
if(d%3>1) len2++;
}
int l1=l+1, r1=l1+len1-1, l2=r1+1, r2=l2+len2-1, l3=r2+1, r3=r-1;
for(int i=parl;i<=parr;i++)
{
if(i<=l) write(num,i,fewer(bag));
else if(r<=i) write(num,i,fewer(bag^1));
else
{
if(l1<=i && i<=r1) write(num,i,child(num,1));
else if(l2<=i && i<=r2) write(num,i,child(num,2));
else if(l3<=i && i<=r3) write(num,i,child(num,3));
}
}
rec(child(num,1),bag^1,l1,r1,l,r);
rec(child(num,2),bag^1,l2,r2,l,r);
rec(child(num,3),bag^1,l3,r3,l,r);
}
std::vector<std::vector<int>> devise_strategy(int n)
{
s.resize(21, vector<int>(n+1,0));
for(int i=0;i<=20;i++) s[i][0]=((i+2)/3)%2;
rec(0,0,1,n,1,n);
return s;
}
