#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 200;
int count_mushrooms(int n) {
if (n <= 2000) {
int cnt = 1;
vector<int> a, b;
a.push_back(0);
int mx = 0;
for (int i = 1; i < n; i++) {
vector<int> m = {0, i};
int res = use_machine(m);
if (!res) cnt++, a.push_back(i);
else b.push_back(i);
++mx;
if (a.size() >= 100 || b.size() >= 100) break;
}
bool f = 0;
if (a.size() < b.size()) f = 1, swap(a, b);
int sz = a.size();
// for (int i : b) t.push_back(i);
for (int i = mx + 1; i < n; i += sz - 1) {
vector<int> v;
int it = 0, tested = 0;
for (int j = i; j <= min(n-1, i + sz-1 - 1); j++) {
v.push_back(a[it++]);
v.push_back(j);
tested++;
}
while (it < a.size()) v.push_back(a[it++]);
int res = use_machine(v);
if (!f) cnt += (tested - res / 2);
else cnt += (res / 2);
}
return cnt;
}
int cnt = 1;
vector<int> a, b;
a.push_back(0);
int mx = 0;
for (int i = 1; i < n; i += 3) {
vector<int> m = {0, i, i+1, i+2};
int res = use_machine(m);
if (!res) {
cnt += 3;
a.push_back(i); a.push_back(i+1); a.push_back(i+2);
} else if (res == 3) {
cnt += 1;
b.push_back(i); a.push_back(i+1); b.push_back(i+2);
} else if (res == 1) {
b.push_back(i+2);
vector<int> m = {0, i};
res = use_machine(m);
if (res) {
b.push_back(i);
b.push_back(i+1);
} else {
cnt++;
a.push_back(i);
m = {0, i+1};
res = use_machine(m);
if (!res) {
cnt++;
a.push_back(i+1);
} else b.push_back(i+1);
}
} else if (res == 2) {
cnt++;
a.push_back(i+2);
vector<int> m = {0, i};
res = use_machine(m);
if (!res) {
cnt++;
a.push_back(i);
b.push_back(i+1);
} else {
b.push_back(i);
m = {0, i+1};
res = use_machine(m);
if (!res) {
cnt++;
a.push_back(i+1);
} else {
b.push_back(i+1);
}
}
}
mx += 3;
if (a.size() >= 138 || b.size() >= 138) break;
}
bool f = 0;
if (a.size() < b.size()) f = 1, swap(a, b);
int sz = a.size();
// for (int i : b) t.push_back(i);
for (int i = mx + 1; i < n; i += sz - 1) {
vector<int> v;
int it = 0, tested = 0;
for (int j = i; j <= min(n-1, i + sz-1 - 1); j++) {
v.push_back(a[it++]);
v.push_back(j);
tested++;
}
while (it < a.size()) v.push_back(a[it++]);
int res = use_machine(v);
if (!f) cnt += (tested - res / 2);
else cnt += (res / 2);
}
return cnt;
}
