#include "insects.h"
#include <vector>
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;
while (l < r - 1) {
int x = (l + r) / 2;
for (int i = 0; i < N; i++) {
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;
for (int i = 0; i < N; i++) {
cnt = 0;
if (in[i]) {
move_outside(i);
in[i] = false;
}
}
}
}
return l;
}
