#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int M = 121;
/*
5
0 1 1 0 1
*/
int count_mushrooms(int n) {
vector<int> cl(n, -1);
cl[0] = 1;
if (n == 2)
{
return 2 - use_machine({0, 1});
}
cl[1] = 1 - use_machine({0, 1});
cl[2] = 1 - use_machine({0, 2});
bool t;
int x, y;
if (cl[0] == cl[1])
{
t = true;
x = 0;
y = 1;
}
else if (cl[0] == cl[2])
{
t = true;
x = 0;
y = 2;
}
else
{
t = false;
x = 1;
y = 2;
}
for (int i = 3; i < min(n - 1, M); i += 2)
{
int res = use_machine({x, i, y, i + 1});
if (res == 0)
{
cl[i] = cl[i + 1] = t;
}
else if (res == 1)
{
cl[i] = t;
cl[i + 1] = !t;
}
else if (res == 2)
{
cl[i] = !t;
cl[i + 1] = t;
}
else
{
cl[i] = cl[i + 1] = !t;
}
}
if (n < M && n % 2 == 0)
{
cl[n - 1] = 1 - use_machine({0, n - 1});
}
int ans = 0;
if (n < M)
{
for (int i = 0; i < n; i++)
ans += cl[i];
return ans;
}
int as = 0;
for (int i = 0; i < M; i++)
{
as += cl[i];
}
ans += as;
bool cs = as > M / 2;
vector<int> ch;
for (int i = 0; i < M; i++)
{
if (cl[i] == cs)
{
ch.push_back(i);
}
}
if (ch.size() % 2 == 1)
{
ch.pop_back();
}
int len = ch.size() / 2;
for (int i = M; i < n; i += len)
{
vector<int> q;
for (int j = 0; j < min(len, n - i); j++)
{
q.push_back(ch[j * 2]);
q.push_back(i + j);
q.push_back(ch[j * 2 + 1]);
}
int res = use_machine(q) / 2;
ans += !cs ? res : len - res;
//cout << '-' << i << ' ' << res << endl;
}
return ans;
}
