#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector<vector<int>> ids(2);
ids[0].push_back(0);
int ans = 1;
for (int i = 1; i < n; i++) {
if (ids[0].size() > ids[1].size()) {
vector<int> qv(1, ids[0][0]);
int k = min(n, i + (int) ids[0].size());
for (int j = i; j < k; j++) {
qv.push_back(j);
if (j != k - 1) {
qv.push_back(ids[0][j - i + 1]);
}
}
int cc = use_machine(qv);
if (cc % 2 == 1) {
ids[1].push_back(qv.back());
}
ans += (k - i) - (cc + 1) / 2;
i = k - 1;
} else {
vector<int> qv(1, ids[1][0]);
int k = min(n, i + (int) ids[1].size());
for (int j = i; j < k; j++) {
qv.push_back(j);
if (j != k - 1) {
qv.push_back(ids[1][j - i + 1]);
}
}
int cc = use_machine(qv);
if (cc % 2 == 1) {
ids[0].push_back(qv.back());
}
ans += (cc + 1) / 2;
i = k - 1;
}
}
return ans;
}
