#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int N) {
if (N == 2) {
return 2 - use_machine({0, 1});
}
vector<int> a, p(N - 1);
int mn = 1e9;
iota(p.begin(), p.end(), 1);
for (int i = 0; i < 100; i++) {
shuffle(p.begin(), p.end(), rng);
int x = use_machine(p);
if (x < mn) {
mn = x;
a = p;
}
}
int ans = 1;
for (int i = 0; i < N - 1;) {
bool f = use_machine({0, a[i]}) == 0;
vector<int> p{a[i]};
if (f) {
ans++;
}
if (++i == N - 1) {
break;
}
for (int j = 0; ; j++) {
if (i + (1 << j) > N - 1) {
j = -1;
continue;
}
for (int k = i; k < i + (1 << j); k++) {
p.push_back(a[k]);
}
if (use_machine(p) != 0) {
if (j == 0) {
break;
}
for (int k = 0; k < (1 << j); k++) {
p.pop_back();
}
j = -1;
} else {
if (f) {
ans += 1 << j;
}
i += 1 << j;
}
}
}
return ans;
}
