#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int count_mushrooms(int n) {
vector<int> type[2];
int flag = 0, cur = 1, k = -1, best = 1e9, cnt[2] = {0, 0};
type[0].push_back(0);
for(int i = 2; i <= n; i++) {
int numQ = 2 + i - 2 + (n - (2 * i - 1) + i - 1) / i;
if (numQ < best) {
best = numQ;
k = i;
}
}
//cerr << "k: " << k << endl;
while (cur < n) {
if (type[0].size() < type[1].size()) {
flag ^= 1;
swap(type[0], type[1]);
swap(cnt[0], cnt[1]);
}
if ((int) type[0].size() < k) {
int num = min(2, min(n - cur, (int) type[0].size()));
vector<int> a;
for(int i = 0; i < num; i++) {
a.push_back(cur + i);
a.push_back(type[0][i]);
}
int x = use_machine(a);
for(int i = 0; i < num; i++)
type[(x >> i) & 1].push_back(cur + i);
cur += num;
} else {
int num = min(n - cur, (int) type[0].size());
vector<int> a;
for(int i = 0; i < num; i++) {
a.push_back(cur + i);
a.push_back(type[0][i]);
}
int x = use_machine(a);
type[x & 1].push_back(cur);
cnt[1] += x / 2;
cnt[0] += (num - 1) - x / 2;
cur += num;
}
}
if (flag) {
flag ^= 1;
swap(type[0], type[1]);
swap(cnt[0], cnt[1]);
}
return cnt[0] + type[0].size();
}
