#include "mushrooms.h"
using namespace std;
#define pb push_back
int count_mushrooms(int n) {
int answer;
int cnt0=1, cnt1=0;
vector<int> ones, zeros={0};
vector<bool> known(n+1, 0);
known[0]=1;
int val;
vector<int> m = {0};
for(int i=1; i<min(300, n); i+=2){
m.pb(i);
m.pb(i+1);
val = use_machine(m);
if(val==0){
// {0,0,0}
cnt0+=2;
zeros.pb(i);
zeros.pb(i+1);
known[i]=1;
known[i+1]=1;
} else if(val==1){
// {0,_,1}
cnt1++;
ones.pb(i+1);
known[i+1]=1;
} else if(val==2){
// {0,1,0}
cnt0++;cnt1++;
zeros.pb(i);
ones.pb(i+1);
known[i]=1;
known[i+1]=1;
}
m = {0};
}
int next_unknown = 1;
while(known[next_unknown])next_unknown++;
if(cnt0 >= cnt1){
answer = n-cnt1;
while(next_unknown < n){
m = {zeros[0]};
for(int i=1; i<cnt0; i++){
if(next_unknown >= n)break;
m.pb(next_unknown);
m.pb(zeros[i]);
known[next_unknown]=true;
while(known[next_unknown])next_unknown++;
}
answer -= use_machine(m)/2;
}
return answer;
} else{
answer = cnt0;
while(next_unknown < n){
m = {ones[0]};
for(int i=1; i<cnt1; i++){
if(next_unknown >= n)break;
m.pb(next_unknown);
m.pb(ones[i]);
known[next_unknown]=true;
while(known[next_unknown])next_unknown++;
}
answer += use_machine(m)/2;
}
return answer;
}
}
