#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int use_machine(std::vector<int> x);
int count_mushrooms(int n) {
int ans = 0;
vector<int> a {0}, b; //specific zeros and ones
int S = sqrt(n), K = 0;
for(int i = 1; i < min(S + 2, n); i++){
vector<int> v {0, i};
int val = use_machine(v);
if(val==0){
a.pb(i);
}else{
b.pb(i);
}
K = i;
}
if(a.size() < b.size()){
S = b.size();
S--;
for(int i = K + 1; i + S <= n; i += S){
vector<int> v {b[0]};
int ind = 1;
for(int j = i; j < i + S; ++j){
v.pb(j), v.pb(b[ind++]);
K = j;
}
int val = use_machine(v);
ans += val/2;
}
if(K + 1 < n){
vector<int> v {b[0]};
int ind = 1;
for(int j = K + 1; j < n; ++j){
v.pb(j), v.pb(b[ind++]);
}
int val = use_machine(v);
ans += val / 2;
}
}else{
S = a.size();
S--;
// cout << S <<"S" << K << endl;;
for(int i = K + 1; i + S <= n; i += S){
vector<int> v {a[0]};
int ind = 1;
for(int j = i; j < i + S; ++j){
v.pb(j), v.pb(a[ind++]);
K = j;
}
int val = use_machine(v);
ans += S - val/2;
}
if(K + 1 < n){
vector<int> v {a[0]};
int ind = 1;
for(int j = K + 1; j < n; ++j){
v.pb(j), v.pb(a[ind++]);
}
int val = use_machine(v);
ans += S - val / 2;
}
}
return ans + a.size();
}
