#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int count_mushrooms(int N) {
int ans = 1;
int root = min(N - 1, 200);
vector <vector <int>> by_type(2);
by_type[0].push_back(0);
for (int i = 1; i <= root; i++) {
int tmp = use_machine({0, i});
by_type[tmp].push_back(i);
ans += !tmp;
}
bool swapped = false;
if (by_type[0].size() > by_type[1].size()) {
swap(by_type[0], by_type[1]);
swapped = true;
}
int sz = by_type[1].size();
for (int i = root + 1; i < N; i += sz - 1) {
vector <int> v = {by_type[1][0]};
for (int j = i; j < min(N, i + sz - 1); j++) {
v.push_back(j);
v.push_back(by_type[1][j - i + 1]);
}
int tmp = use_machine(v) / 2;
ans += swapped ? (int)v.size() / 2 - tmp : tmp;
}
return ans;
}
