#include <bits/stdc++.h>
#include "mushrooms.h"
template <class T> using Vec = std::vector<T>;
int count_mushrooms(int n) {
Vec<int> a, b;
a.push_back(0);
for (int i = 1; i < std::min(n, 200); ++i) {
(use_machine(Vec<int>{0, i}) ? b : a).push_back(i);
}
bool flip = false;
if (a.size() < b.size()) {
flip = true;
std::swap(a, b);
}
const int len = (int) a.size();
int ret = len;
int seen = std::min(n, 200);
while (seen < n) {
Vec<int> ask;
for (int i = 0; i < len and seen < n; ++i) {
ask.push_back(a[i]);
ask.push_back(seen++);
}
ret += (int) ask.size() / 2;
ret -= (use_machine(ask) + 1) / 2;
}
return flip ? n - ret : ret;
}
