#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
const int C = 20000;
vector<int> a(1, 0);
vector<int> b;
int res = 1;
int ptr = 1;
while ((int) a.size() < C || (int) b.size() < C) {
if (ptr >= n) {
break;
}
if (a.size() > b.size()) {
int c = min(n - ptr, (int) a.size());
vector<int> qv;
for (int i = 0; i < c; i++) {
qv.push_back(a[i]);
qv.push_back(ptr + i);
}
int d = use_machine(qv);
if (d % 2 == 0) {
a.push_back(qv.back());
res += 1;
} else {
b.push_back(qv.back());
}
res += (c - 1 - (d / 2));
ptr += c;
} else {
int c = min(n - ptr, (int) b.size());
vector<int> qv;
for (int i = 0; i < c; i++) {
qv.push_back(b[i]);
qv.push_back(ptr + i);
}
int d = use_machine(qv);
if (d % 2 == 0) {
b.push_back(qv.back());
} else {
a.push_back(qv.back());
res += 1;
}
res += d / 2;
ptr += c;
}
}
return res;
}
