#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 2e4;
ll has = 1;
vector<ll> A, B;
int count_mushrooms(int n) {
A.pb(0);
ll k = min(n, 300);
for(ll i = 1; i < k; i++)
{
vector<int> tmp;
tmp.pb(0);
tmp.pb(i);
ll tmp2 = use_machine(tmp);
has += (1 - tmp2);
if(!tmp2)
A.pb(i);
else
B.pb(i);
}
if(A.size() > B.size())
{
ll sz = A.size();
for(ll i = k; i < n; i += (sz - 1))
{
ll byk = 0;
vector<int> tmp;
for(ll j = 0; j < (sz - 1); j++)
{
if(i + j >= n)
break;
byk++;
tmp.pb(A[j]);
tmp.pb(i + j);
}
tmp.pb(A[sz - 1]);
ll tmp2 = use_machine(tmp);
tmp2 /= 2;
has += (byk - tmp2);
}
}
else
{
ll sz = B.size();
for(ll i = k; i < n; i += (sz - 1))
{
ll byk = 0;
vector<int> tmp;
for(ll j = 0; j < (sz - 1); j++)
{
if(i + j >= n)
break;
byk++;
tmp.pb(B[j]);
tmp.pb(i + j);
}
tmp.pb(B[sz - 1]);
ll tmp2 = use_machine(tmp);
tmp2 /= 2;
has += tmp2;
}
}
return has;
}
