#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 200;
int count_mushrooms(int n) {
int cnt = 1;
vector<int> a, b;
a.push_back(0);
int mx = 0;
for (int i = 1; i < n; i++) {
vector<int> m = {0, i};
int res = use_machine(m);
if (!res) cnt++, a.push_back(i);
else b.push_back(i);
++mx;
if (a.size() >= 100 || b.size() >= 100) break;
}
bool f = 0;
if (a.size() < b.size()) f = 1, swap(a, b);
int sz = a.size();
// for (int i : b) t.push_back(i);
for (int i = mx + 1; i < n; i += sz - 1) {
vector<int> v;
int it = 0, tested = 0;
for (int j = i; j <= min(n-1, i + sz-1 - 1); j++) {
v.push_back(a[it++]);
v.push_back(j);
tested++;
}
while (it < a.size()) v.push_back(a[it++]);
int res = use_machine(v);
if (!f) cnt += (tested - res / 2);
else cnt += (res / 2);
}
return cnt;
}
