#include "mushrooms.h"
#include <vector>
#include <iostream>
using namespace std;
const int X = 199; //199
int ceil_div(int a, int b)
{
return a/b + bool(a%b);
}
int count_mushrooms(int n)
{
if(n <= 227)
{
int ans = 1;
for(int i = 1; i < n; i++) ans += !use_machine(vector<int>{0, i});
return ans;
}
vector<int> typ[2];
typ[0].push_back(0);
for(int i = 1; i <= 2; i++)
typ[ use_machine(vector<int>{0, i}) ].push_back(i);
int B = 0;
if(int(typ[1].size()) >= 2) B = 1;
int maxV = 0;
for(int i = 3; i+1 <= min(n-1, X); i += 2)
{
int U = use_machine(vector<int>{typ[B][0], i, typ[B][1], i+1});
if(B == 0)
{
typ[U/2].push_back(i);
typ[U%2].push_back(i+1);
}
else
{
typ[!(U/2)].push_back(i);
typ[!(U%2)].push_back(i+1);
}
maxV = i+1;
}
vector<int> ans{(int)typ[0].size(), (int)typ[1].size()};
int base = (int)typ[0].size() > (int)typ[1].size() ? 0 : 1;
int ct = (int)typ[base].size();
// cerr << ans[0] << ' ' << ans[1] << '\n';
for(int v = 1+maxV; v < n; v += ct-1)
{
// cerr << "V = " << v << '\n';
vector<int> query{typ[base][0]};
for(int i = v; i < v+ct-1 && i < n; i++)
{
query.push_back(i);
query.push_back(typ[base][i-v+1]);
}
int Q = use_machine(query);
int rem = (int)query.size() - 1 - Q;
ans[base] += rem/2;
ans[!base] += Q/2;
}
return ans[0];
}
