#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define desr 100
int count_mushrooms(int n) {
vector<int> ata;
vector<int> bta;
ata.push_back(0);
int klk=1;
int cur=1;
while (true)
{
if (cur==n-1 || (ata.size()<2 && bta.size()<2) )
{
vector<int> qu(2);
qu[0]=0;
qu[1]=cur;
int ans=use_machine(qu);
if (ans==0)
{
ata.push_back(cur);
klk++;
}
else
{
bta.push_back(cur);
}
cur++;
}
else if (ata.size()>=2)
{
vector<int> qu(4);
qu[0]=cur;
qu[1]=ata[0];
qu[2]=cur+1;
qu[3]=ata[1];
int ans=use_machine(qu);
if (ans%2==0)
{
ata.push_back(cur);
klk++;
}
else
{
bta.push_back(cur);
ans--;
}
if (ans==0)
{
ata.push_back(cur+1);
klk++;
}
else
{
bta.push_back(cur+1);
}
cur+=2;
}
else
{
vector<int> qu(4);
qu[0]=cur;
qu[1]=bta[0];
qu[2]=cur+1;
qu[3]=bta[1];
int ans=use_machine(qu);
if (ans%2==1)
{
ans--;
ata.push_back(cur);
klk++;
}
else
{
bta.push_back(cur);
}
if (ans==2)
{
ata.push_back(cur+1);
klk++;
}
else
{
bta.push_back(cur+1);
}
cur+=2;
}
if (ata.size()+bta.size()==n) return klk;
if (ata.size()>=desr) break;
if (bta.size()>=desr) break;
}
//cout<<klk<<" "<<cur<<"\n";
while (cur<n)
{
int sz=n-cur;
if (sz<ata.size())
{
///prosto dovyrshi
vector<int> qu(2*sz+1);
for (int q=0;q<sz;q++)
{
qu[2*q]=ata[q];
qu[2*q+1]=cur+q;
}
qu[2*sz]=ata[sz];
int ans=use_machine(qu);
klk+=(sz-ans/2);
cur=n;
}
else if (sz<bta.size())
{
///prosto dovyrshi
vector<int> qu(2*sz+1);
for (int q=0;q<sz;q++)
{
qu[2*q]=bta[q];
qu[2*q+1]=cur+q;
}
qu[2*sz]=bta[sz];
int ans=use_machine(qu);
klk+=(ans/2);
cur=n;
}
else if (ata.size()>bta.size())
{
//cerr<<"a e "<<ata.size()<<"\n";
sz=ata.size();
vector<int> qu(2*sz);
for (int q=0;q<sz;q++)
{
qu[2*q]=cur+q;
qu[2*q+1]=ata[q];
}
int ans=use_machine(qu);
if (ans%2==0)
{
///cur e A
ata.push_back(cur);
}
else
{
bta.push_back(cur);
ans++;
}
klk+=(sz-ans/2);
cur+=sz;
//cout<<klk<<"\n";
}
else
{
//cerr<<"b e "<<bta.size()<<"\n";
sz=bta.size();
vector<int> qu(2*sz);
for (int q=0;q<sz;q++)
{
qu[2*q]=cur+q;
qu[2*q+1]=bta[q];
}
int ans=use_machine(qu);
if (ans%2==1)
{
///cur e A
ans++;
ata.push_back(cur);
}
else bta.push_back(cur);
klk+=(ans/2);
cur+=sz;
}
}
return klk;
}
