#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 2e3+3, inf = INT_MAX;
mt19937 rng((time(nullptr)) + (chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));
int n, m, ans;
vector<int> v;
bitset<N> vis;
int min_cardinality(int N) {
// move_inside(i);
// move_outside(i);
// press_button(i);
n = N;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = i;
// Busco los primeros
m = 0;
for (int i = 0; i < n; i++) {
move_inside(i);
vis[i] = 1;
m++;
if (press_button() > 1) {
move_outside(i);
vis[i] = 0;
m--;
}
}
if (m == 1) return n;
int l = 1;
int r = n/m;
while (l < r) {
shuffle(all(v), rng);
int mid = (l+r)>>1;
int taken = m;
for (int i = 0; i < n && taken + (n-i) >= m*mid && taken < m*mid; i++) {
int x = v[i];
if (vis[x]) continue;
move_inside(x);
taken++;
if (press_button() > mid) {
move_outside(x);
taken--;
}
}
if (taken == m*mid) l = mid+1;
else r = mid;
}
return l;
}
