#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 10;
const int block = 180;
int type[maxn];
int count_mushrooms(int n)
{
vector < int > A, B;
A.push_back(0);
for (int i = 1; i < min(n, 4); i ++)
{
vector < int > tmp;
tmp.push_back(0);
tmp.push_back(i);
if (use_machine(tmp) == 0)
A.push_back(i);
else
B.push_back(i);
}
if (n <= block)
{
for (int i = 4; i < n; i ++)
{
vector < int > tmp;
tmp.push_back(0);
tmp.push_back(i);
if (use_machine(tmp) == 0)
A.push_back(i);
}
return A.size();
}
if (A.size() > 1)
{
for (int i = 4; i < min(n - 1, block); i += 2)
{
vector < int > tmp;
tmp.push_back(A[0]);
tmp.push_back(i);
tmp.push_back(A[1]);
tmp.push_back(i + 1);
int val = use_machine(tmp);
if (val % 2 == 1)
B.push_back(i + 1);
else
A.push_back(i + 1);
if (val > 1)
B.push_back(i);
else
A.push_back(i);
}
}
else
{
for (int i = 4; i < block; i += 2)
{
vector < int > tmp;
tmp.push_back(B[0]);
tmp.push_back(i);
tmp.push_back(B[1]);
tmp.push_back(i + 1);
int val = use_machine(tmp);
if (val % 2 == 1)
A.push_back(i + 1);
else
B.push_back(i + 1);
if (val > 1)
A.push_back(i);
else
B.push_back(i);
}
}
int cntA = 0, cntB = 0;
int i = block;
while(i < n)
{
int j = min(n, (int)i + (int)max(A.size(), B.size())), len = j - i;
if (A.size() > B.size())
{
vector < int > tmp;
for (int f = 0; f < len; f ++)
{
tmp.push_back(A[f]);
tmp.push_back(i + f);
}
int val = use_machine(tmp);
if (val % 2 == 1)
{
B.push_back(j - 1);
val --;
}
else
cntA ++;
///cout << len << " : " << val << endl;
cntB = cntB + val / 2;
cntA = cntA + (len - 1) - val / 2;
}
else
{
vector < int > tmp;
for (int f = 0; f < len; f ++)
{
tmp.push_back(B[f]);
tmp.push_back(i + f);
}
int val = use_machine(tmp);
if (val % 2 == 1)
{
A.push_back(j - 1);
val --;
}
else
cntB ++;
cntA = cntA + val / 2;
cntB = cntB + (len - 1) - val / 2;
}
i = j;
}
return cntA + A.size();
}
