#include "mushrooms.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int inf = 1e9 + 7;
int count_mushrooms(int n) {
int ca = 1, cb = 0;
vector<int> a = {0}, b;
int num = 1;
for (int i = 1; i < min(n,200); i++) {
vector<int> q = {0, i};
int x = use_machine(q);
if (x == 0) {
ca++;
a.push_back(i);
} else {
cb++;
b.push_back(i);
}
num++;
}
if (num == n) {
return ca;
}
if (ca > cb) {
int res = ca;
for (int i = num; i < n; i += (ca)) {
vector<int> q(ca * 2);
for (int j = 0; j < ca; j++) {
q[j * 2] = a[j];
}
int ind = -1;
int pos = 0;
for (int j = 1; j < q.size(); j += 2) {
q[j] = i + (j - 1) / 2;
if (q[j] >= n) {
ind = j;
break;
} else {
pos++;
}
}
if (ind != -1) {
int cur = q.size() - 1;
while (cur >= ind) {
q.pop_back();
cur--;
}
}
int x = use_machine(q);
res += (pos) - (x + 1) / 2;
}
return res;
} else {
int res = ca;
for (int i = num; i < n; i += (cb)) {
vector<int> q(cb * 2);
for (int j = 0; j < cb; j++) {
q[j * 2] = b[j];
}
int ind = -1;
for (int j = 1; j < q.size(); j += 2) {
q[j] = i + (j - 1) / 2;
if (q[j] >= n) {
ind = j;
break;
}
}
if (ind != -1) {
int cur = q.size() - 1;
while (cur >= ind) {
q.pop_back();
cur--;
}
}
int x = use_machine(q);
res += (x + 1) / 2;
}
return res;
}
}
