#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 k1 = min(n, 3);
ll k2 = min(n, 155);
for(ll i = 1; i < k1; 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())
{
for(ll i = k1; i < k2; i += 2)
{
vector<int> tmp;
tmp.pb(A[0]);
tmp.pb(i);
tmp.pb(A[1]);
if(i + 1 < k2)
tmp.pb(i + 1);
ll tmp2 = use_machine(tmp);
if(tmp2 & 2)
B.pb(i);
else
{
has++;
A.pb(i);
}
if(i + 1 < k2)
{
if(tmp2 & 1)
B.pb(i + 1);
else
{
has++;
A.pb(i + 1);
}
}
}
}
else
{
for(ll i = k1; i < k2; i += 2)
{
vector<int> tmp;
tmp.pb(B[0]);
tmp.pb(i);
tmp.pb(B[1]);
if(i + 1 < k2)
tmp.pb(i + 1);
ll tmp2 = use_machine(tmp);
if(tmp2 & 2)
{
has++;
A.pb(i);
}
else
B.pb(i);
if(i + 1 < k2)
{
if(tmp2 & 1)
{
has++;
A.pb(i + 1);
}
else
B.pb(i + 1);
}
}
}
ll sz = max((ll)A.size(), (ll)B.size());
for(ll i = k2; i < n;)
{
if(A.size() > B.size())
{
ll byk = 0;
vector<int> tmp;
for(ll j = 0; j < sz; j++)
{
if(i + j >= n)
break;
byk++;
tmp.pb(A[j]);
tmp.pb(i + j);
}
ll tmp2 = use_machine(tmp);
if(tmp2 % 2 == 0)
A.pb(i + sz - 1);
else
B.pb(i + sz - 1);
tmp2 = tmp2 / 2 + tmp2 % 2;
has += (byk - tmp2);
}
else
{
ll byk = 0;
vector<int> tmp;
for(ll j = 0; j <sz; j++)
{
if(i + j >= n)
break;
byk++;
tmp.pb(B[j]);
tmp.pb(i + j);
}
ll tmp2 = use_machine(tmp);
if(tmp2 % 2 == 0)
B.pb(i + sz - 1);
else
A.pb(i + sz - 1);
tmp2 = tmp2 / 2 + tmp2 % 2;
has += tmp2;
}
i += sz;
sz = max((ll)A.size(), (ll)B.size());
}
return has;
}
