#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
vector<vector<string>> comb;
vector<map<string,int>> code;
//b個のしきりにa個のボールを挿入、pまで決めた
//各ボールについて前に仕切りが何個あるかという列で組合せを表現
void makecomb(string s,int a,int b){
if(s.size()==a){
code[b][s]=comb[b].size();
comb[b].push_back(s);
return;
}
int la=0;
if(s.size()>0)la=s.back();
for(int i=la;i<=b;i++){
string res=s;
res.push_back(i);
makecomb(res,a,b);
}
}
};
void Anna (int N){
int aa=6,bb=4,cc=aa+bb;
comb.assign(bb+1,vector<string>());
code.assign(bb+1,map<string,int>());
vector<vector<int>>comblim(bb+1,vector<int>(cc+1));
for(int i=1;i<=bb;i++){
for(int j=cc-i;j>=1;j--){
makecomb("",j,i);
comblim[i][j]=comb[i].size()-1;
}
if(i<bb){
for(int k=cc-i;k>=1;k--){
if(comblim[i][k]+cc-i<=comblim[i][1]){
while(comb[i+1].size()<comblim[i][k])comb[i+1].push_back("");//ここ不等号のキラーケース
}
}
}
}
int c=DrawCard(-1);
int cnt[2]={0,0},send=0,b=0;
for(int i=0;i<N-(cc-b);i++){
int o=-1;
if(c==0){
if(cnt[0]<bb){
o=cnt[0];
cnt[0]++;
}
}else{
if(b<bb&&comb[b+1][send]!=""){
o=cnt[0];
cnt[1]++;
b++;
}else{
send++;
}
}
c=DrawCard(o);
}
if(b==0){
for(int i=0;i<cc-b;i++){
int o=-1;
if(c==0){
o=cnt[0];
cnt[c]++;
}
c=DrawCard(o);
}
}else if(cnt[0]<bb){
for(int i=0;i<cc-b;i++){
int o=-1;
if(c==1){
o=cnt[0];
cnt[c]++;
}
c=DrawCard(o);
}
}else if(cnt[1]==0){
for(int i=0;i<cc-b;i++){
c=DrawCard(-1);
}
}else{
int a=cc-b;
while(send>comblim[b][a]){
if(c==1)send++;
c=DrawCard(-1);
a--;
}
int L=bb+b;
int ins[2]={0,0};
string s=comb[b][send];
for(int i=0;i<a;i++){
int o;
if(c==1)o=ins[0]+s[i];
else o=L-ins[1]-s[i];
ins[1-c]++;
L++;
c=DrawCard(o);
}
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
vector<vector<string>> comb;
vector<map<string,int>> code;
//b個のしきりにa個のボールを挿入、pまで決めた
//各ボールについて前に仕切りが何個あるかという列で組合せを表現
void makecomb(string s,int a,int b){
if(s.size()==a){
code[b][s]=comb[b].size();
comb[b].push_back(s);
return;
}
int la=0;
if(s.size()>0)la=s.back();
for(int i=la;i<=b;i++){
string res=s;
res.push_back(i);
makecomb(res,a,b);
}
}
};
int Bruno (int N,int L,vector<int>C){
int aa=6,bb=4,cc=aa+bb;
comb.assign(bb+1,vector<string>());
code.assign(bb+1,map<string,int>());
vector<vector<int>>comblim(bb+1,vector<int>(cc+1));
for(int i=1;i<=bb;i++){
for(int j=cc-i;j>=1;j--){
makecomb("",j,i);
comblim[i][j]=comb[i].size()-1;
}
if(i<bb){
for(int k=cc-i;k>=1;k--){
if(comblim[i][k]+cc-i<=comblim[i][1]){
while(comb[i+1].size()<comblim[i][k])comb[i+1].push_back("");//ここ不等号のキラーケース
}
}
}
}
int cnt[2]={0,0};
for(int i=0;i<L;i++)cnt[C[i]]++;
if(cnt[1]==0)return cc+bb-cnt[0];
if(cnt[0]<bb){
int zero=cnt[0]+(cc-cnt[1]);
return N-zero;
}
if(cnt[1]==0)return 0;
int six=0,cnt0=0;
for(int i=0;i<L;i++){
if(C[i]==0){
if(++cnt0==bb){
six=i;
break;
}
}
}
int b=0;
for(int i=six+1;i<L;i++)b+=C[i];
b=min(bb,b);
int a=L-bb-b;
string s="";
int q=0;
for(int i=0;i<L&&q<b;i++){
if(C[i]==0)q++;
else s.push_back(q);
}
q=0;
for(int i=0;i<L&&q<b;i++){
if(C[L-1-i]==1)q++;
else s.push_back(q);
}
while(s.size()<a)s.push_back(b);
sort(s.begin(),s.end());
return code[b][s]+cnt[1];
}
