#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 20;
const int lim = 140;
vector<int> type[maxn];
int n, res, pt;
void alternate(int k) {
k = min(min(k, n - pt), max((int)type[0].size(), (int)type[1].size()));
if (k == 0) {
return;
}
int t = (int)type[0].size() >= k ? 0 : 1;
vector<int> q;
for (int i = 0; i < k; i++) {
q.push_back(type[t][i]);
q.push_back(pt + i);
}
int cnt = use_machine(q);
if (t == 0) {
res += k - (cnt + 1) / 2;
}
else {
res += (cnt + 1) / 2;
}
type[t ^ (cnt & 1)].push_back(pt + k - 1);
if (k == 2) {
type[t ^ (cnt >> 1)].push_back(pt);
}
pt += k;
}
int count_mushrooms(int _n) {
n = _n;
type[0].push_back(0);
res = 1;
pt = 1;
while (pt < n && (int)type[0].size() < lim && (int)type[1].size() < lim) {
alternate(2);
}
while (pt < n) {
alternate(n);
}
return res;
}
