#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> outside;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
outside.push_back(i);
}
}
int d = n - outside.size();
auto check = [&](int b) -> bool {
vector<int> moved_inside;
vector<int> new_outside;
shuffle(outside.begin(), outside.end(), rng);
for (int i : outside) {
if (n - outside.size() + moved_inside.size() == d * b || n - outside.size() + moved_inside.size() + ( outside.size() - moved_inside.size() - new_outside.size() ) < d * b) {
new_outside.push_back(i);
continue;
}
move_inside(i);
if (press_button() > b) {
move_outside(i);
new_outside.push_back(i);
} else {
moved_inside.push_back(i);
}
}
if (n - new_outside.size() == d * b) {
outside = new_outside;
return true;
} else {
for (int i : moved_inside) {
move_outside(i);
}
return false;
}
};
int l = 1;
int r = n / d;
while (l < r) {
int m = (l + r + 1) >> 1;
if (check(m)) {
l = m;
} else {
r = m - 1;
}
}
return l;
}
