#include "mushrooms.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
int count_mushrooms(int n) {
int Min=INT_MAX;
int M=-1;
for(int N=1;N<=n;N++){
int c=N+2*(n-N)/N;
if(Min>c){
M=N;
Min=c;
}
}
if(n<=3)M=n;
//~ cout<<Min<<' '<<M<<endl;
vector<int>black,white;
black.push_back(0);
for(int i=1;i<M;i++){
vector<int>v={0,i};
int c=use_machine(v);
if(c==0)black.push_back(i);
else white.push_back(i);
}
vector<int>idx=(black.size()>white.size()?black:white);
int ans=0;
int rest=n-M;
int cur=M;
while(rest){
int d=min(rest,(int)idx.size()-1);
vector<int>v;
rep(i,d){
v.push_back(idx[i]);
v.push_back(cur+i);
}
v.push_back(idx.back());
int c=use_machine(v);
assert(c%2==0);
ans+=c/2;
cur+=d;
rest-=d;
}
if(black.size()>white.size()){
return n-(white.size()+ans);
}
else{
return black.size()+ans;
}
}
