#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int k = 93;
int count_mushrooms(int n) {
vector<int> m(n);
if (n <= k) {
for (int i = 1; i < n; i++) {
m[i] = use_machine({0, i});
}
return count(m.begin(), m.end(), 0);
}
m[1] = use_machine({0, 1});
m[2] = use_machine({0, 2});
vector<int> sm;
if (!m[1]) {
sm = {0, 1};
} else if (!m[2]) {
sm = {0, 2};
} else {
sm = {1, 2};
}
for (int i = 3; i + 1 < 2 * k - 1; i += 2) {
int x = use_machine({sm[0], i, sm[1], i + 1});
if (x == 0) {
m[i] = m[i + 1] = m[sm[0]];
} else if (x == 1) {
m[i] = m[sm[0]];
m[i + 1] = !m[sm[0]];
} else if (x == 2) {
m[i] = !m[sm[0]];
m[i + 1] = m[sm[0]];
} else if (x == 3) {
m[i] = m[i + 1] = !m[sm[0]];
}
}
int dom;
if (count(m.begin(), m.begin() + 2 * k - 1, 0) > count(m.begin(), m.begin() + 2 * k - 1, 1)) dom = 0;
else dom = 1;
sm.clear();
for (int i = 0; i < 2 * k - 1; i++) {
if (m[i] == dom) {
sm.pb(i);
}
}
int ans = count(m.begin(), m.begin() + 2 * k - 1, 0);
for (int i = 2 * k - 1; i < n; ) {
vector<int> cur;
for (int j = i; j < min(n, i + (int)sm.size()); j++) {
cur.pb(j);
cur.pb(sm[j - i]);
}
int tmp = use_machine(cur);
if (tmp % 2 == 0) {
sm.pb(i);
}
int diff = (tmp + 1) / 2;
if (dom == 0) {
ans += (int)cur.size() / 2 - diff;
} else {
ans += diff;
}
i += (int)cur.size() / 2;
}
return ans;
}
