#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> vec[2];
int count_mushrooms(int nn) {
n = nn;
vec[0].push_back(0);
if(n <= 273)
{
for(int i = 1 ; i < n ; i++)
{
int c = use_machine({0 , i});
vec[c].push_back(i);
}
return vec[0].size();
}
vec[use_machine({0 , 1})].push_back(1);
vec[use_machine({0 , 2})].push_back(2);
if(vec[0].size() < vec[1].size())
swap(vec[0] , vec[1]);
int m = min(n , 273);
for(int i = 3 ; i + 1 < m ; i += 2)
{
int c = use_machine({vec[0][0] , i , vec[0][1] , i + 1});
vec[c % 2].push_back(i + 1);
vec[c / 2].push_back(i);
}
if(vec[0].size() < vec[1].size())
swap(vec[0] , vec[1]);
vector <int> rem;
for(int i = m ; i < n ; i++)
rem.push_back(i);
int cnt[2];
cnt[0] = cnt[1] = 0;
while(!rem.empty())
{
vector <int> m;
int tmp = 0;
for(auto u : vec[0])
{
m.push_back(u);
if(!rem.empty())
{
m.push_back(rem.back());
rem.pop_back();
tmp++;
}
}
int c = use_machine(m);
int val = (c + 1) / 2;
cnt[1] += val;
cnt[0] += tmp - val;
}
if(vec[0][0] == 0)
return cnt[0] + vec[0].size();
else
return cnt[1] + vec[1].size();
}
