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