#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
#define pb push_back
#define sz(x) (int)x.size()
int k=40;
int count_mushrooms(int n){
vector<int> a,b,v;
a.pb(0);
for(int i=1;i<n;++i)v.pb(i);
int na=1;
while(!v.empty()){
vector<int> g;
if(sz(a)>=sz(b)){
int x=sz(a);
if(2<=x&&x<=k)x=2;
for(int i=0;i<x;++i){
if(v.empty())break;
g.pb(a[i]);
g.pb(v.back());
v.pop_back();
}
int res=use_machine(g);
na+=sz(g)/2-(res+1)/2;
if(res%2)b.pb(g.back());
else a.pb(g.back());
if(x==2){
if(res>=2)b.pb(g[1]);
else a.pb(g[1]);
}
}
else{
int x=sz(b);
if(2<=x&&x<=k)x=2;
for(int i=0;i<x;++i){
if(v.empty())break;
g.pb(b[i]);
g.pb(v.back());
v.pop_back();
}
int res=use_machine(g);
na+=(res+1)/2;
if(res%2)a.pb(g.back());
else b.pb(g.back());
if(x==2){
if(res>=2)a.pb(g[1]);
else b.pb(g[1]);
}
}
}
return na;
}
