#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;
if (n == 2) {
vector<int> q = {0, 1};
int x = use_machine(q);
if (x == 0) {
return 2;
} else {
return 1;
}
}
int num = 1;
for (int i = 1; i < min(n - 1,6); i+= 2) {
vector<int> q = {i + 1, 0, i};
int x = use_machine(q);
if (x == 0) {
ca += 2;
a.push_back(i);
a.push_back(i + 1);
} else if (x == 2) {
cb += 2;
b.push_back(i);
b.push_back(i + 1);
} else {
ca++;
cb++;
q = {i, 0};
x = use_machine(q);
if (x == 0) {
a.push_back(i);
b.push_back(i + 1);
} else {
a.push_back(i + 1);
b.push_back(i);
}
}
num+= 2;
}
if (num == n) {
return ca;
}
if (ca > cb) {
int res = ca;
for (int i = num; i < n; i += (ca - 1)) {
vector<int> q(ca * 2 - 1);
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 / 2;
}
return res;
} else {
int res = ca;
for (int i = num; i < n; i += (cb - 1)) {
vector<int> q(cb * 2 - 1);
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 / 2;
}
return res;
}
}
