#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int N) {
if (N == 2) {
return 2 - use_machine({0, 1});
}
vector<int> p(N);
iota(p.begin(), p.end(), 0);
for (int i = 0; i < 3; i++) {
shuffle(p.begin(), p.end(), rng);
use_machine(p);
}
int A = use_machine({0, 1});
int B = use_machine({0, 2});
int C = 0;
vector<int> T[2];
T[0].push_back(0);
T[A].push_back(1);
T[B].push_back(2);
if (A == 0) {
A = 0;
B = 1;
} else if (B == 0) {
A = 0;
B = 2;
} else {
A = 1;
B = 2;
C = 1;
}
int i = 3;
for (; i + 1 < N && i <= 281; i += 2) {
int x = use_machine({A, i, B, i + 1});
T[C ^ (x > 1)].push_back(i);
T[C ^ (x % 2)].push_back(i + 1);
}
if (T[0].size() > T[1].size()) {
C = 0;
} else {
C = 1;
}
int M = T[C].size(), ans = T[0].size();
for (; i < N;) {
int K = min(N - i, M - 1);
vector<int> v;
for (int j = 0; j < K; j++) {
v.push_back(T[C][j]);
v.push_back(i++);
}
v.push_back(T[C][K]);
int x = use_machine(v) / 2;
if (C) {
ans += x;
} else {
ans += K - x;
}
}
return ans;
}
