#include "insects.h"
#include <bits/stdc++.h>

int a[2005], b[2005];

int min_cardinality(int N) {
	int col = 0;
	for (int i = 0; i < N; ++i) {
		move_inside(i);
		if (i && press_button() > 1) move_outside(i);
		else ++col, a[i] = 1;
	}
	int L = 1, R = N, num = col;
	while (L <= R) {
		int mid = (L + R) >> 1;
		for (int i = 0; i < N; ++i)
			if (!a[i] && !b[i]) {
				move_inside(i);
				if (press_button() > mid) move_outside(i);
				else a[i] = 2, ++num;
				if (num >= col * mid) break;
			}
		if (num >= col * mid) {
			L = mid + 1;
			for (int i = 0; i < N; ++i) if (a[i] == 2) a[i] = 1;
		} else {
			R = num / col;
			for (int i = 0; i < N; ++i) if (a[i] == 2) move_outside(i), a[i] = 0; else b[i] = 1;
		}
	}
	return R;
}