#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> A, B, tmp;
int count_mushrooms(int N)
{
int num=sqrt(2*N), ans;
A.push_back(0);
for (int i=1; i<num; i++)
{
tmp.clear();
tmp.push_back(0);
tmp.push_back(i);
if (use_machine(tmp))
B.push_back(i);
else
A.push_back(i);
}
ans=A.size();
if (A.size()>=B.size())
{
int sz=A.size();
for (int l=num, r=num+sz-1; l<N; l+=sz, r+=sz)
{
r=min(r, N-1);
tmp.clear();
for (int i=l; i<=r; i++)
{
tmp.push_back(A[i-l]);
tmp.push_back(i);
}
ans+=r-l+1-(use_machine(tmp)+1)/2;
}
}
else
{
int sz=B.size();
for (int l=num, r=num+sz-1; l<N; l+=sz, r+=sz)
{
r=min(r, N-1);
tmp.clear();
for (int i=l; i<=r; i++)
{
tmp.push_back(B[i-l]);
tmp.push_back(i);
}
ans+=(use_machine(tmp)+1)/2;
}
}
return ans;
}
