#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int use_machine(std::vector<int> x);
int count_mushrooms(int n) {
int c[2] = {0, 0};
vector<int> v[2]; v[0].push_back(0);
v[use_machine({0, 1})].push_back(1);
if(n == 2) return v[0].size();
v[use_machine({0, 2})].push_back(2);
if(n == 3) return v[0].size();
int u = 3, k = v[0].size() > v[1].size() ? 0 : 1;
for(int i=0;i<100 && u+1<n;i++, u += 2) {
int re = use_machine({v[k][0], u, v[k][1], u+1});
v[k ^ (re >> 1)].push_back(u);
v[k ^ (re & 1)].push_back(u+1);
}
while(u < n) {
int k = v[0].size() > v[1].size() ? 0 : 1;
vector<int> q;
for(int i=0;i<v[k].size() && u<n;i++) {
q.push_back(v[k][i]);
q.push_back(u++);
}
int re = use_machine(q);
v[k ^ (re % 2)].push_back(q.back());
int S = q.size()/2-1; re /= 2;
c[k] += S-re, c[!k] += re;
}
return v[0].size() + c[0];
}
