#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
int count_mushrooms(int n) {
vector<int> m;
vector<int> a, b;
int id = 1;
a.emplace_back(0);
while(max(a.size(), b.size()) < sqrt(n) && id < n) {
int t = use_machine({0, id});
if(t == 1) {
b.emplace_back(id);
}
else a.emplace_back(id);
id++;
}
int ans = a.size();
if(a.size() > b.size()) {
for(int i = id; i < n; i += a.size() - 1) {
int l = i, r = min(n - 1, (int)(i + a.size() - 2));
m.clear();
m.emplace_back(a[0]);
for(int j = l; j <= r; j++) {
m.emplace_back(j);
m.emplace_back(a[j - l + 1]);
}
int t = use_machine(m);
ans += (r - l + 1) - (t / 2);
}
}
else {
for(int i = id; i < n; i += b.size() - 1) {
int l = i, r = min(n - 1, (int)(i + b.size() - 2));
m.clear();
m.emplace_back(b[0]);
for(int j = l; j <= r; j++) {
m.emplace_back(j);
m.emplace_back(b[j - l + 1]);
}
int t = use_machine(m);
ans += (t / 2);
}
}
return ans;
}
