#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int B=200;
int count_mushrooms(int N) {
vector<int> posA, posB;
posA.push_back(0);
for(int i=1;i+1<min(N,B);i+=2) {
int r=use_machine({i,0,i+1});
if(r==0) {
posA.push_back(i);
posA.push_back(i+1);
} else if(r==1) {
if(use_machine({0,i})==0) {
posA.push_back(i);
posB.push_back(i+1);
} else {
posB.push_back(i);
posA.push_back(i+1);
}
} else {
posB.push_back(i);
posB.push_back(i+1);
}
}
if((min(N,B)-1)&1) {
if(use_machine({0,min(N,B)-1})==0) {
posA.push_back(min(N,B)-1);
} else {
posB.push_back(min(N,B)-1);
}
}
int ans=posA.size();
if(posA.size()>posB.size()) {
int s=posA.size();
for(int i=B;i<N;i+=s) {
vector<int> qry;
for(int j=i;j<min(N,i+s);j++) {
qry.push_back(posA[j-i]);
qry.push_back(j);
}
int w=use_machine(qry);
w=(w+1)/2;
ans+=(qry.size()/2-w);
}
} else {
int s=posB.size();
for(int i=B;i<N;i+=s) {
vector<int> qry;
for(int j=i;j<min(N,i+s);j++) {
qry.push_back(posB[j-i]);
qry.push_back(j);
}
int w=use_machine(qry);
w=(w+1)/2;
ans+=w;
}
}
return ans;
}
