#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int BLOCK = 100;
vector<int> A, B;
int count_mushrooms(int n) {
if(n <= BLOCK * 2){
int ans = 1;
for (int i = 1; i < n; i++)
{
ans += use_machine({0, i}) == 0;
}
return ans;
}
A.push_back(0);
bool swp = false;
for (int i = 1; i < BLOCK * 2; ++i)
{
bool b = use_machine({0, i}) == 1;
if(b){
B.push_back(i);
}
else{
A.push_back(i);
}
}
int ans = A.size();
int cnt = 0;
if(A.size() < B.size()) {
swp = true;
swap(A, B);
}
for (int i = BLOCK * 2; i < n; i += A.size())
{
vector<int> v;
for(int j = i; j < min(n, i + int(A.size())); ++j){
v.push_back(A[j - i]);
v.push_back(j);
}
cnt += (use_machine(v) + 1) / 2;
}
if(!swp){
cnt = (n - BLOCK * 2) - cnt;
}
ans += cnt;
return ans;
}
