#include "mushrooms.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int k = 142;
int count_mushrooms(int n)
{
int A = 0, B = 0;
// small case
if (n <= 226)
{
A = 1;
for (int i = 1; i < n; i++)
if (!use_machine({0, i}))
A++;
return A;
}
vector<int> a, b;
a.emplace_back(0);
for (int i = 1; i < 3; i++)
if (use_machine({0, i}))
b.push_back(i);
else
a.push_back(i);
if (a.size() >= 2)
{
int a1 = a[0], a2 = a[1];
for (int i = 3; i < 2 * k - 1; i += 2)
{
int result = use_machine({a1, i, a2, i + 1});
if (result == 0)
a.push_back(i), a.push_back(i + 1);
else if (result == 1)
a.push_back(i), b.push_back(i + 1);
else if (result == 2)
b.push_back(i), a.push_back(i + 1);
else if (result == 3)
b.push_back(i), b.push_back(i + 1);
}
}
else
{
int b1 = b[0], b2 = b[1];
for (int i = 3; i < 2 * k - 1; i += 2)
{
int result = use_machine({b1, i, b2, i + 1});
if (result == 3)
a.push_back(i), a.push_back(i + 1);
else if (result == 2)
a.push_back(i), b.push_back(i + 1);
else if (result == 1)
b.push_back(i), a.push_back(i + 1);
else if (result == 0)
b.push_back(i), b.push_back(i + 1);
}
}
// not too small case
if (n <= 2 * k - 1)
return a.size();
// big case
if (a.size() >= k)
{
for (int i = 2 * k - 1; i < n; i += k)
{
vector<int> q;
for (int j = 0; j < k && i + j < n; j++)
{
q.emplace_back(a[j]);
q.emplace_back(i + j);
}
B += (use_machine(q) + 1) / 2;
}
return n - (int)b.size() - B;
}
else
{
for (int i = 2 * k - 1; i < n; i += k)
{
vector<int> q;
for (int j = 0; j < k && i + j < n; j++)
{
q.emplace_back(b[j]);
q.emplace_back(i + j);
}
A += (use_machine(q) + 1) / 2;
}
return a.size() + A;
}
}
