#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int LIM = 140;
int count_mushrooms(int n)
{
vector<int> v[2];
v[0].push_back(0);
int ult=0;
for(int i=1;i<n;i++)
{
if(i+1==n || ((int)v[0].size()<=1 && (int)v[1].size()<=1))
{
v[0].push_back(i);
if(use_machine(v[0])==0)
{
}
else
{
v[0].pop_back();
v[1].push_back(i);
}
}
else
{
if((int)v[0].size() >= 2)
{
vector<int> newv;
newv = v[0];
newv.pop_back();
newv.push_back(i);
newv.push_back(v[0].back());
newv.push_back(i+1);
int x = use_machine(newv);
if(x==0)
{
v[0].push_back(i);
v[0].push_back(i+1);
}
else if(x==1)
{
v[0].push_back(i);
v[1].push_back(i+1);
}
else if(x==2)
{
v[1].push_back(i);
v[0].push_back(i+1);
}
else if(x==3)
{
v[1].push_back(i);
v[1].push_back(i+1);
}
}
else
{
assert((int)v[1].size() >= 2);
vector<int> newv;
newv = v[1];
newv.pop_back();
newv.push_back(i);
newv.push_back(v[1].back());
newv.push_back(i+1);
int x = use_machine(newv);
if(x==0)
{
v[1].push_back(i);
v[1].push_back(i+1);
}
else if(x==1)
{
v[1].push_back(i);
v[0].push_back(i+1);
}
else if(x==2)
{
v[0].push_back(i);
v[1].push_back(i+1);
}
else if(x==3)
{
v[0].push_back(i);
v[0].push_back(i+1);
}
}
i++;
}
ult = i;
if(max(v[0].size(), v[1].size()) >= LIM)
break;
}
if(ult==n-1)
return v[0].size();
int cnt = v[0].size();
if(v[1].size() >= LIM)
{
assert(v[1].size() >= LIM);
for(int i=ult+1;i<n;i+=v[1].size())
{
vector<int> newv;
for(int j=0;j<v[1].size();j++)
{
newv.push_back(v[1][j]);
if(i+j < n) newv.push_back(i+j);
}
int x = use_machine(newv);
cnt += (x+1)/2;
}
}
else
{
assert(v[0].size() >= LIM);
for(int i=ult+1;i<n;i+=v[0].size())
{
vector<int> newv;
int posibile=0;
for(int j=0;j<v[0].size();j++)
{
newv.push_back(v[0][j]);
if(i+j < n)
{
newv.push_back(i+j);
posibile++;
if(j+1 < v[0].size())
posibile++;
}
}
int x = posibile - use_machine(newv);
cnt += (x+1)/2;
}
}
return cnt;
}
