#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector<int> a = {0};
vector<int> b;
int cnta = 1;
int pos = 1;
while (pos < n) {
vector<int> q;
if (a.size() > b.size()) {
int f = min(n - pos, (int) a.size());
for (int i = 0; i < f; i++) {
q.push_back(a[i]);
q.push_back(pos++);
}
int res = use_machine(q);
if (res & 1) {
b.push_back(q.back());
} else a.push_back(q.back());
cnta += f - (res + 1) / 2;
} else {
int f = min(n - pos, (int) b.size());
for (int i = 0; i < f; i++) {
q.push_back(b[i]);
q.push_back(pos++);
}
int res = use_machine(q);
if (res & 1) {
a.push_back(q.back());
} else b.push_back(q.back());
cnta += (res + 1) / 2;
}
}
return cnta;
}
