#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int N) {
if (N <= 5) {
int ans = N;
for (int i = 1; i < N; i++) {
ans -= use_machine({0, i});
}
return ans;
}
vector<int> T[] = {{0}, {}};
T[use_machine({0, 1})].push_back(1);
T[use_machine({0, 2})].push_back(2);
int z = T[1].size() >= 2, i = 3, x;
x = use_machine({T[z][0], i, T[z][1], i + 1});
T[x >> 1 & 1 ^ z].push_back(i++);
T[x >> 0 & 1 ^ z].push_back(i++);
while (0 && i + 2 < N && (T[0].size() < 2 || T[1].size() < 2)) {
z = T[1].size() >= 3;
x = use_machine({T[z][0], i + 1, T[z][1], i + 2, T[z][2], i});
T[x & 1 ^ z].push_back(i++);
if (~x & 2) {
T[x >> 2 & 1 ^ z].push_back(i++);
T[x >> 2 & 1 ^ z].push_back(i++);
} else {
x = use_machine({0, i});
T[x ^ 0].push_back(i++);
T[x ^ 1].push_back(i++);
}
}
for (z = T[1].size() >= 3; i + 4 < N && i <= 100 && 0;) {
x = use_machine({T[z][0], i + 1, T[z][1], i + 2, T[z][2], i});
T[x & 1 ^ z].push_back(i++);
if (~x & 2) {
T[x >> 2 & 1 ^ z].push_back(i++);
T[x >> 2 & 1 ^ z].push_back(i++);
} else {
x = use_machine({T[z ^ 1][0], i, T[z ^ 1][1], T[z][0], i + 1, T[z][1], i + 2, T[z][2], i + 3}) - 1;
T[x >> 2 & 1 ^ z ^ 1].push_back(i++);
T[x >> 2 & 1 ^ z].push_back(i++);
T[x >> 1 & 1 ^ z].push_back(i++);
T[x >> 0 & 1 ^ z].push_back(i++);
}
}
int ans = T[0].size();
while (i < N) {
z = T[1].size() > T[0].size();
int K = min(N - i, (int)T[z].size());
vector<int> v;
for (int j = 0; j < K; j++) {
v.push_back(T[z][j]);
v.push_back(i++);
}
x = use_machine(v);
if (z) {
ans += x / 2 + x % 2;
} else {
ans += K - x / 2 - x % 2;
}
T[x & 1 ^ z].push_back(i - 1);
}
return ans;
}
