#include "insects.h"
#include <vector>
#include <numeric>
using namespace std;
int min_cardinality(int N) {
int k = 0, cnt = 0;
vector<char> in(N);
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() == 1) {
++k;
++cnt;
in[i] = true;
}
else
move_outside(i);
}
int l = 1, r = N / k + 1;
vector<int> possible;
iota(possible.begin(), possible.end(), 0);
while (l < r - 1) {
int x = (l + r) / 2;
for (int i : possible) {
if (!in[i]) {
move_inside(i);
if (press_button() > x)
move_outside(i);
else {
++cnt;
in[i] = true;
}
}
}
if (cnt == k * x) {
l = x;
} else {
r = x;
possible.clear();
cnt = 0;
for (int i = 0; i < N; i++) if (in[i]) {
move_outside(i);
in[i] = false;
possible.push_back(i);
}
}
}
return l;
}
