#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int solve(vector<int> v) {
assert(!v.empty());
v.pb(0);
int q = use_machine(v);
v.pop_back();
if (q == 0) {
return v.size();
} else if (q == (int)v.size()) {
return ((int)v.size() + 1) / 2 - 1;
}
vector<int> lh, rh;
for (int i = 0; i < (int)v.size(); i++) {
if (i < (int)v.size() / 2) {
lh.pb(v[i]);
} else {
rh.pb(v[i]);
}
}
return solve(lh) + solve(rh);
}
int count_mushrooms(int n) {
vector<int> v(n - 1);
iota(v.begin(), v.end(), 1);
return 1 + solve(v);
}
