#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector <int> a;
for (int i = 1; i < n; i++)
a.push_back(i);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(a.begin(), a.end(), rng);
int ans = 1;
vector <int> A = {0}, B;
while (!a.empty()) {
vector <int> v;
if ((int)A.size() >= (int)B.size()) {
int t = 0;
for (int i = 0; i < (int) A.size() && !a.empty(); i++) {
t++;
v.push_back(a.back());
v.push_back(A[i]);
a.pop_back();
}
int k = use_machine (v);
if (k % 2)
B.push_back(v[0]);
else
A.push_back(v[0]);
k = t - ((k + 1) / 2);
ans += k;
} else {
int t = 0;
for (int i = 0; i < (int) B.size() && !a.empty(); i++) {
t++;
v.push_back(a.back());
v.push_back(B[i]);
a.pop_back();
}
int k = use_machine (v);
if (k % 2)
A.push_back(v[0]);
else
B.push_back(v[0]);
k = ((k + 1) / 2);
ans += k;
}
}
return ans;
}
