#include "insects.h"
#include <vector>
int min_cardinality(int N) {
std::vector<int> in;
for (int i = 0; i < N; ++i) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
} else {
in.push_back(i);
}
}
int kinds = (int)in.size();
for (int i : in) {
move_outside(i);
}
auto check = [&](int thres) {
in.clear();
for (int i = 0; i < N; ++i) {
move_inside(i);
if (press_button() > thres) {
move_outside(i);
} else {
in.push_back(i);
}
}
for (int i : in) {
move_outside(i);
}
return (int)in.size() == kinds * thres;
};
int ok = 1, ng = N / kinds + 1;
while (ng - ok > 1) {
int md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
return ok;
}
