#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int calc(int n, int L)
{
int mxm=0;
for(int cate=L;cate<=2*L;cate++)
{
mxm = max(mxm, cate + (n-cate+1)/L);
}
return mxm;
}
int count_mushrooms(int n)
{
int LIM=-1,best=100000;
for(int L=1;L<=min(n,300);L++)
{
if(calc(n,L) < best)
{
best = calc(n,L);
LIM = L;
}
}
vector<int> v[2];
v[0].push_back(0);
int ult=0;
for(int i=1;i<n;i++)
{
v[0].push_back(i);
if(use_machine(v[0])==0)
{
}
else
{
v[0].pop_back();
v[1].push_back(i);
}
ult = i;
if(max(v[0].size(), v[1].size()) >= LIM)
break;
}
if(ult==n-1)
return v[0].size();
int cnt = v[0].size();
if(v[1].size() >= LIM)
{
assert(v[1].size() >= LIM);
for(int i=ult+1;i<n;i+=v[1].size())
{
vector<int> newv;
for(int j=0;j<v[1].size();j++)
{
newv.push_back(v[1][j]);
if(i+j < n) newv.push_back(i+j);
}
int x = use_machine(newv);
cnt += (x+1)/2;
}
}
else
{
assert(v[0].size() >= LIM);
for(int i=ult+1;i<n;i+=v[0].size())
{
vector<int> newv;
int posibile=0;
for(int j=0;j<v[0].size();j++)
{
newv.push_back(v[0][j]);
if(i+j < n)
{
newv.push_back(i+j);
posibile++;
if(j+1 < v[0].size())
posibile++;
}
}
int x = posibile - use_machine(newv);
cnt += (x+1)/2;
}
}
return cnt;
}
