#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int all,be,mid,ed,arr[20005],type,ans=1;
vector<int> v;
void mush(int be,int ed,int val){
if(val == 0 || be == ed) return;
if(val == ed-be){
for(int i=be+1;i<=ed;i++) arr[i] = 1;
return;
}
int mid = (be+ed)/2,f,s;
v.clear();
v.push_back(mid);
v.push_back(mid+1);
if(use_machine(v)){
val--;
arr[mid+1] = 1;
}
v.clear();
for(int i=be;i<=mid;i++) v.push_back(i);
f = use_machine(v);
mush(be,mid,f);
s = val-f;
mush(mid+1,ed,s);
return;
}
int count_mushrooms(int n) {
for (int i = 0; i < n; i++) v.push_back(i);
all = use_machine(v);
mush(0,n-1,all);
type = 0;
for(int i=1;i<n;i++){
type += arr[i];
if(type % 2 == 0) ans++;
}
return ans;
}
