#include"mushrooms.h"
#ifndef EVAL
#include"stub.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n){
vector<int>a,b;
a.push_back(0);
int id=1;
while(/*max(a.size(),b.size())<120&&*/id<n){
if(a.size()>=3&&b.size()>=2&&id+4<n){
int ans1=use_machine({a[0],id,a[1],id+1,a[2],id+2});
if(ans1&1)b.push_back(id+2);
else a.push_back(id+2);
ans1>>=1;
if(ans1==0){
a.push_back(id);
a.push_back(id+1);
id+=3;
}else if(ans1==2){
b.push_back(id);
b.push_back(id+1);
id+=3;
}else{
int ans2=use_machine({b[0],id,b[1],a[0],id+1,a[1],id+3,a[2],id+4})-1;
if(ans2&1)b.push_back(id+4);
else a.push_back(id+4);
ans2>>=1;
if(ans2&1)b.push_back(id+3);
else a.push_back(id+3);
ans2>>=1;
if(ans2&1){
b.push_back(id);
a.push_back(id+1);
}else{
a.push_back(id);
b.push_back(id+1);
}
id+=5;
}
}else if(b.size()>=3&&a.size()>=2&&id+4<n){
int ans1=use_machine({b[0],id,b[1],id+1,b[2],id+2});
if(ans1&1)a.push_back(id+2);
else b.push_back(id+2);
ans1>>=1;
if(ans1==0){
b.push_back(id);
b.push_back(id+1);
id+=3;
}else if(ans1==2){
a.push_back(id);
a.push_back(id+1);
id+=3;
}else{
int ans2=use_machine({a[0],id,a[1],b[0],id+1,b[1],id+3,b[2],id+4})-1;
if(ans2&1)a.push_back(id+4);
else b.push_back(id+4);
ans2>>=1;
if(ans2&1)a.push_back(id+3);
else b.push_back(id+3);
ans2>>=1;
if(ans2&1){
b.push_back(id);
a.push_back(id+1);
}else{
a.push_back(id);
b.push_back(id+1);
}
id+=5;
}
}else if(a.size()>=2&&id+1<n){
int ans=use_machine({a[0],id,a[1],id+1});
if(ans&1)b.push_back(id+1);
else a.push_back(id+1);
ans>>=1;
if(ans&1)b.push_back(id);
else a.push_back(id);
id+=2;
}else if(b.size()>=2&&id+1<n){
int ans=use_machine({b[0],id,b[1],id+1});
if(ans&1)a.push_back(id+1);
else b.push_back(id+1);
ans>>=1;
if(ans&1)a.push_back(id);
else b.push_back(id);
id+=2;
}else{
if(use_machine({0,id}))b.push_back(id);
else a.push_back(id);
id++;
}
}
int res=(int)a.size();
// while(id<n){
// if(a.size()>b.size()){
// vector<int>v;
// for(int i=0;i<a.size()&&id+i<n;i++){
// v.push_back(a[i]);
// v.push_back(id+i);
// }
// id+=int(a.size());
// int ans=use_machine(v);
// if(ans&1)b.push_back(v.back());
// else a.push_back(v.back());
// ans++;
// ans>>=1;
// res+=int(a.size())-ans;
// }else{
// vector<int>v;
// for(int i=0;i<b.size()&&id+i<n;i++){
// v.push_back(b[i]);
// v.push_back(id+i);
// }
// id+=int(b.size());
// int ans=use_machine(v);
// if(ans&1)a.push_back(v.back());
// else b.push_back(v.back());
// ans++;
// ans>>=1;
// res+=ans;
// }
// }
return res;
}
/*
10
0 1 1 0 1 1 1 0 0 1
*/
