#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
int b = max(3, (int) sqrt(n) + 20);
vector<int> ones;
vector<int> zeros = {0};
for (int i = 1; i < min(n, b); ++i) {
if (use_machine({0, i}) == 0) {
zeros.push_back(i);
} else {
ones.push_back(i);
}
}
int cnt = 0;
int p = b;
while (p < n) {
vector<int> ask;
int pv = 1;
if (ones.size() > zeros.size()) {
ask.push_back(ones[0]);
while (p < n && pv < (int) ones.size()) {
ask.push_back(p++);
ask.push_back(ones[pv++]);
}
cnt += use_machine(ask) / 2;
} else {
ask.push_back(zeros[0]);
int tot = 0;
while (p < n && pv < (int) zeros.size()) {
ask.push_back(p++);
ask.push_back(zeros[pv++]);
tot += 2;
}
int tmp = use_machine(ask);
cnt += (tot - tmp) / 2;
}
}
return zeros.size() + cnt;
}
