#include "mushrooms.h"
using namespace std;
const int A = 151;
int count_mushrooms(int n) {
if (n <= A) {
int ans = 1;
for (int i = 1; i < n; i++) {
vector<int> g = {0, i};
ans += !use_machine(g);
}
return ans;
}
vector<int> st(A, 0);
st[1] = use_machine({0, 1});
st[2] = use_machine({0, 2});
int p = 0;
if (st[1] == st[2] && st[1] == 1) {
p = 0;
} else if (st[0] == st[1]) {
p = 1;
}
else {
p = 2;
}
for (int i = 3; i < A; i += 2) {
int res = 0;
if (p) {
res = use_machine({0, i, p, i + 1});
if (res == 0) {
st[i] = st[i + 1] = 0;
}
else if (res == 1) {
st[i + 1] = 1;
}
else if (res == 2) {
st[i] = 1;
}
else {
st[i] = st[i + 1] = 1;
}
}
else {
res = use_machine({1, i, 2, i + 1});
if (res == 0) {
st[i] = st[i + 1] = 1;
}
else if (res == 1) {
st[i] = 1;
}
else if (res == 2) {
st[i + 1] = 1;
}
else {
st[i] = st[i + 1] = 0;
}
}
}
int cnt = 0, ans = 0;
for (int i = 0; i < A; i++) {
ans += !st[i];
cnt += st[i];
}
vector<int> g[2];
int t = (cnt > A / 2);
for (int i = 0; i < A; i++) {
if (st[i] == t) {
g[0].push_back(i);
} else {
g[1].push_back(i);
}
}
vector<int> rem;
for (int i = A; i < n; i++) {
rem.push_back(i);
}
while (!rem.empty()) {
if (g[0].size() < g[1].size()) {
t = 1 - t;
swap(g[0], g[1]);
}
vector<int> x;
while (!rem.empty() && !g[0].empty()) {
x.push_back(rem.back());
x.push_back(g[0].back());
rem.pop_back();
g[0].pop_back();
}
int res = use_machine(x);
if (res % 2 == 1) {
res++;
g[1].push_back(x[0]);
}
else {
g[0].push_back(x[0]);
}
res /= 2;
if (t == 1) {
ans += res;
} else {
int sz = (int)x.size();
sz /= 2;
ans += sz - res;
}
while (!x.empty()) {
g[0].push_back(x.back());
x.pop_back(); x.pop_back();
}
}
return ans;
}
