#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int get_ans(int sz, int ans, int x){
if(x == 0) return sz / 2 - (ans + 1) / 2;
return (ans + 1) / 2;
}
int count_mushrooms(int n){
int x = 0;
vector<int> pos[2];
int k = 80;
pos[x].push_back(0);
for(int i=1; i<3; i++){
vector<int> ask = {0, i};
if(use_machine(ask) == 0){
pos[0].push_back(i);
} else pos[1].push_back(i);
}
int cnt = 2 * k - 1;
while(cnt >= n) cnt -= 2;
for(int i=3; i<cnt; i+=2){
if((int) pos[1 - x].size() > (int) pos[x].size()) x = 1 - x;
vector<int> ask = {pos[x][0], i, pos[x][1], i + 1};
int cur = use_machine(ask);
if(cur % 2 == 1){
pos[1 - x].push_back(i + 1);
} else pos[x].push_back(i + 1);
cur /= 2;
if(cur == 1){
pos[1 - x].push_back(i);
} else pos[x].push_back(i);
}
int tot = (int) pos[0].size();
for(int i=cnt; i<n; i++){
if((int) pos[1 - x].size() > (int) pos[x].size()) x = 1 - x;
vector<int> ask;
int sz = (int) pos[x].size();
for(int j=i; j<min(i + sz, n); j++){
ask.push_back(pos[x][j - i]);
ask.push_back(j);
}
i = min(i + sz, n) - 1;
int cur = use_machine(ask);
tot += get_ans((int) ask.size(), cur, x);
if(cur % 2 == 1){
pos[1 - x].push_back(i);
} else pos[x].push_back(i);
}
return tot;
}
