#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
mt19937 rng(678147511);
int count_mushrooms(int n) {
vector<int> a, b, order;
a.push_back(0);
for (int i = 1; i < n; i ++)
order.push_back(i);
shuffle(order.begin(), order.end(), rng);
int ans = 1;
while (order.size()){
if (a.size() > b.size()){
vector<int> vec;
int sz = min(a.size(), order.size());
for (int i = 0; i < sz; i ++){
vec.push_back(order.back());
vec.push_back(a[i]);
order.pop_back();
}
int val = use_machine(vec);
if (val % 2)
b.push_back(vec[0]);
else
a.push_back(vec[0]);
ans += sz - (val + 1) / 2;
}
else{
vector<int> vec;
int sz = min(b.size(), order.size());
for (int i = 0; i < sz; i ++){
vec.push_back(order.back());
vec.push_back(b[i]);
order.pop_back();
}
int val = use_machine(vec);
if (val % 2)
a.push_back(vec[0]);
else
b.push_back(vec[0]);
ans += (val + 1) / 2;
}
}
return ans;
}
