// In the name of Allah
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 20000 + 4;
const int M = 100;
vector<int> ls[2], lsx;
int col[maxn];
int count_mushrooms(int n) {
int sz = 0;
for (int i = 0; i < n; i++) {
if (i == 0) col[i] = 0;
else if (use_machine({0, i}) == 1) col[i] = 1;
else col[i] = 0;
ls[col[i]].pb(i); sz++;
if (max(len(ls[0]), len(ls[1])) >= M) break;
}
int res = len(ls[0]);
if (n <= sz) return res;
int mx = max(len(ls[0]), len(ls[1]));
for (int i = sz; i < n; i += mx) {
lsx.clear();
for (int j = i; j < min(n, i + mx); j++) {
lsx.pb(j);
if (len(ls[0]) >= len(ls[1])) lsx.pb(ls[0][j - i]);
else lsx.pb(ls[1][j - i]);
}
int t1 = (use_machine(lsx) + 1) / 2, t2 = (min(n, i + mx) - i) - t1;
if (len(ls[0]) >= len(ls[1])) res += t2;
else res += t1;
}
return res;
}
