#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
bool isA;
const int k = min(n, max(3, ((int)sqrt(n * 2)))), a = 0, b = 1;
int nrA, pos1, pos2, bs;
vector <int> s(n), pos;
if (n <= 10) {
nrA = 1;
for (int i = 1; i < n; i++)
nrA += 1 - use_machine({0, i});
return nrA;
}
s[0] = a;
s[1] = use_machine({ 0, 1 }) == 0 ? a : b;
s[2] = use_machine({ 0, 2 }) == 0 ? a : b;
nrA = (s[0] == a) + (s[1] == a) + (s[2] == a);
if (nrA == 1) {
isA = false;
pos1 = 1;
pos2 = 2;
} else {
isA = true;
pos1 = 0;
pos2 = (s[1] == a ? 1 : 2);
}
for (int i = 3; i < k; i += 2) {
int r = use_machine({pos1, i, pos2, i + 1});
if (r == 0)
s[i] = s[i + 1] = (isA ? a : b);
else if (r == 1) {
s[i] = (isA ? a : b);
s[i + 1] = (isA ? b : a);
} else if (r == 2) {
s[i] = (isA ? b : a);
s[i + 1] = (isA ? a : b);
} else
s[i] = s[i + 1] = (isA ? b : a);
}
for (int i = 3; i < k; i++)
nrA += (s[i] == a);
if (nrA > k / 2) {
bs = nrA - 1;
isA = true;
} else {
bs = k - nrA - 1;
isA = false;
}
for (int i = 0; i < k; i++) {
if (s[i] == (isA ? a : b))
pos.push_back(i);
}
for (int i = k; i < n; i += bs) {
int j;
vector <int> m;
for (j = 0; j + 1 < (int)pos.size() && i + j < n; j++) {
m.push_back(pos[j]);
m.push_back(i + j);
}
m.push_back(pos.back());
if (isA)
nrA += j - use_machine(m) / 2;
else
nrA += use_machine(m) / 2;
}
return nrA;
}
