#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
constexpr int lim = 100;
int count_mushrooms(int n) {
int res = 1;
vector<int> a = {0}, b, s;
for (int i = 1; i < n; i++) {
s.push_back(i);
}
while (max(a.size(), b.size()) < lim && !s.empty()) {
int x = s.back();
if (use_machine({0, x}) == 0) {
res++;
a.push_back(x);
} else {
b.push_back(x);
}
s.pop_back();
}
vector<int> k = (a.size() == lim ? a : b);
while (!s.empty()) {
int m = min(lim, (int)s.size());
vector<int> t, v;
for (int i = 0; i < m; i++) {
t.push_back(k[i]);
v.push_back(s.back());
t.push_back(s.back());
s.pop_back();
}
int cnt = use_machine(t);
if (a.size() == lim) {
if (cnt == 0) {
a.insert(a.end(), v.begin(), v.end());
}
if (cnt & 1) {
b.push_back(v.back());
}
res += m - (cnt + 1) / 2;
} else {
if (cnt == 0) {
b.insert(b.end(), v.begin(), v.end());
}
if (cnt & 1) {
a.push_back(v.back());
}
res += (cnt + 1) / 2;
}
}
return res;
}
