#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
if(n<=4)
{
int ans=1;
for(int i=1;i<n;i++)
{
vector<int>v;
v.push_back(0);v.push_back(i);
if(use_machine(v)==0)ans++;
}
return ans;
}
vector<int>qr;
int a=0, b=0, x=0, i, j;
qr.push_back(0);
qr.push_back(1);
int ans1=use_machine(qr);
qr.pop_back();
qr.push_back(2);
int ans2=use_machine(qr);
vector<int>v1, v2;
if(ans1&&ans2)
{
v2.push_back(0);
x=1;
v1.push_back(1);v1.push_back(2);
a=1;
b=2;
}
else if(ans1)
{
v1.push_back(0);v1.push_back(2);
v2.push_back(1);
a=0;
b=2;
}
else if(ans2)
{
v1.push_back(0);v1.push_back(1);
v2.push_back(2);
a=0;
b=1;
}
else
{
v1.push_back(0);v1.push_back(1);v2.push_back(2);
a=0;
b=1;
}
int bu=(int)sqrt(n);
for(i=1;i++<bu;)
{
vector<int>v;
v.push_back(a);
v.push_back(2*i-1);
v.push_back(b);
v.push_back(2*i);
int ans=use_machine(v);
if(ans>=2)v2.push_back(2*i-1);
else v1.push_back(2*i-1);
if(ans%2==1)v2.push_back(2*i);
else v1.push_back(2*i);
}
if(v1.size()<v2.size())
{
v1.clear();
while(v2.size())v1.push_back(v2.back()),v2.pop_back();
x=1-x;
}
int ans=v1.size();
for(i=2*bu+1;i<n;i+=v1.size())
{
vector<int>v;
for(j=i;j<min(i+(int)v1.size(), n);j++)
{
v.push_back(v1[j-i]);
v.push_back(j);
}
int q=use_machine(v);
ans+=v.size()/2;
ans-=(q/2+q%2);
}
if(x==1)return n-ans;
else return ans;
}
