#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int n = N;
vector<int> in(n);
vector<int> roots;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
} else {
roots.push_back(i);
in[i] = true;
}
}
assert((int) roots.size() > 0);
if ((int) roots.size() < 9) {
int res = 1234567;
for (int i = 0; i < (int) roots.size(); i++) {
move_outside(roots[i]);
}
for (int it = 0; it < (int) roots.size(); it++) {
move_inside(roots[it]);
int cnt = 1;
for (int j = 0; j < n; j++) {
if (j == roots[it]) {
continue;
}
move_inside(j);
if (press_button() == 2) {
cnt++;
}
move_outside(j);
}
res = min(res, cnt);
move_outside(roots[it]);
}
return res;
}
auto Check = [&](int mid) {
vector<int> cnt;
for (int i = 0; i < n; i++) {
if (in[i]) {
continue;
}
move_inside(i);
if (press_button() > mid) {
move_outside(i);
} else {
cnt.push_back(i);
}
}
for (int i = 0; i < (int) cnt.size(); i++) {
move_outside(cnt[i]);
}
if ((int) cnt.size() == (mid - 1) * (int) roots.size()) {
return true;
}
return false;
};
int low = 1, high = n / (int) roots.size();
while (low <= high) {
int mid = low + (high - low) / 2;
if (Check(mid)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
--low;
return low;
}
