#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);
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);
}
}
if(a.size() < b.size()){
S = b.size();
S--;
for(int i = S + 2; 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++]);
}
int val = use_machine(v);
ans += v.size() - val/2;
}
if((n-1)%S != 0){
vector<int> v {b[0]};
int ind = 1;
for(int j = (n-1)/S*S+1; j < n; ++j){
v.pb(j), v.pb(b[ind++]);
}
int val = use_machine(v);
ans += v.size() - val/2;
}
}else{
S = a.size();
S--;
for(int i = S + 2; 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++]);
}
int val = use_machine(v);
ans += val/2;
}
if((n-1)%S != 0){
vector<int> v {a[0]};
int ind = 1;
for(int j = (n-1)/S*S+1; j < n; ++j){
v.pb(j), v.pb(a[ind++]);
}
int val = use_machine(v);
ans += val / 2;
}
}
return ans + a.size();
}
