#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector<int> v = {0};
vector<int> A, B;
A.push_back(0);
int T = min(300, n);
for(int i = 1; i < T; i++) {
v.push_back(i);
if (!use_machine(v)) A.push_back(i);
else B.push_back(i);
v.pop_back();
}
bool ok = 0;
int tmp = 0;
if (A.size() < B.size()) swap(A, B), ok = 1;
int sz = A.size(), cnt = 0;
for(int i = T; i < n; i += sz) {
vector<int> ask;
for(int j = i; j < n && j < i + sz; j++) {
ask.push_back(A[j - i]);
ask.push_back(j);
cnt++;
}
tmp += (use_machine(ask) + 1) / 2;
}
if (!ok) return A.size() + cnt - tmp;
return B.size() + tmp;
}
