#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int X=90;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int count_mushrooms(int n){
int p=1;
vector<int> a(1, 0), b;
while (a.size()<X&&b.size()<X&&p<n){
if (a.size()>=2&&p+1<n){
vector<int> temp;
temp.pb(a[0]);
temp.pb(p);
++p;
temp.pb(a[1]);
temp.pb(p);
++p;
int res=use_machine(temp);
if (res&1)b.pb(p-1);
else a.pb(p-1);
if (res&2)b.pb(p-2);
else a.pb(p-2);
}
else if (b.size()>=2&&p+1<n){
vector<int> temp;
temp.pb(b[0]);
temp.pb(p);
++p;
temp.pb(b[1]);
temp.pb(p);
++p;
int res=use_machine(temp);
if (res&1)a.pb(p-1);
else b.pb(p-1);
if (res&2)a.pb(p-2);
else b.pb(p-2);
}
else{
vector<int> temp;
temp.pb(a[0]);
temp.pb(p);
int res=use_machine(temp);
if (res)b.pb(p);
else a.pb(p);
++p;
}
}
int ans=a.size();
while (p<n){
if (a.size()>=b.size()){
vector<int> temp;
for (int i=0; i<a.size()&&p<n; ++i)temp.pb(a[i]), temp.pb(p), ++p;
int res=use_machine(temp);
ans+=temp.size()/2-(res/2+res%2);
if (res%2)b.pb(p-1);
else a.pb(p-1);
}
else{
vector<int> temp;
for (int i=0; i<b.size()&&p<n; ++i)temp.pb(b[i]), temp.pb(p), ++p;
int res=use_machine(temp);
ans+=res/2+res%2;
if (res%2)a.pb(p-1);
else b.pb(p-1);
}
}
return ans;
}
