#include <bits/stdc++.h>
#include "mushrooms.h"
//~ #include "stub.cpp"
using namespace std;
int count_mushrooms(int n){
vector <int> p[2];
p[0].push_back(0);
for(int i = 1 ; i < min(n, 3) ; i++){
int x = use_machine({0, i});
p[x].push_back(i);
}
int idx = 3;
int k = 90;
while(idx + 1 < n && (int)max(p[0].size(), p[1].size()) < k){
int f = 0;
if(p[f].size() < 2) f = 1;
int x = use_machine({p[f][0], idx, p[f][1], idx + 1});
p[(x % 2) ^ f].push_back(idx + 1);
p[(x > 1) ^ f].push_back(idx);
idx += 2;
}
if(idx == n - 1){
int x = use_machine({0, idx});
p[x].push_back(idx);
return p[0].size();
}
int ret = p[0].size();
while(idx < n){
int f = 0;
if(p[1].size() > p[0].size()) f = 1;
vector <int> cur;
for(auto &i : p[f]){
if(idx == n) break;
cur.push_back(i);
cur.push_back(idx++);
}
int x = use_machine(cur);
p[f ^ (x % 2)].push_back(cur.back());
int diff = (x + 1) / 2;
if(f == 1) ret += diff;
else ret += cur.size() / 2 - diff;
}
return ret;
}
