#include "insects.h" #include <bits/stdc++.h> using namespace std; int min_cardinality(int N) { int cnt = 0; vector<bool> f(N); for (int i = 0; i < N; i++) { move_inside(i); if (press_button() <= 1) { f[i] = 1; cnt++; } else { move_outside(i); } } int lo = 1, hi = N / cnt, in = cnt; while (lo < hi) { int mi = (lo + hi + 1) / 2; for (int i = 0; i < N; i++) { if (f[i]) { continue; } move_inside(i); if (press_button() <= mi) { in++; f[i] = 1; } else { move_outside(i); } } if (in == mi * cnt) { lo = mi; } else { for (int i = 0; i < N; i++) { if (f[i]) { move_outside(i); } } in = 0; hi = mi - 1; } } return lo; }