#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e3 + 9;
bool removed[maxn] = { 0 };
vector <int> in_machine;
mt19937 rng(19812034);
int min_cardinality(int n) {
vector <int> m(n);
for (int i = 0; i < n; i++) m[i] = i;
// Find group
int i;
for (int y = 0; y < n; y++)
{
i = m[y];
move_inside(i);
if (press_button() > 1) {
move_outside(i);
} else {
in_machine.emplace_back(i);
removed[i] = true;
}
}
int g = in_machine.size();
int l = 1, r = n / g;
int mid, ans = 0;
while (l != r)
{
mid = (l + r + 1) >> 1;
vector <int> taken_out, taken_in;
int i;
for (int y = 0; y < n; y++)
{
i = m[y];
if (removed[i]) continue;
move_inside(i);
if (press_button() > mid) {
taken_out.emplace_back(i);
move_outside(i);
} else {
taken_in.emplace_back(i);
in_machine.emplace_back(i);
}
}
if ((int)in_machine.size() == mid * g)
{
// Mid is lowerbound
l = mid;
ans = mid;
for (int i : taken_in) removed[i] = true;
} else {
r = mid - 1;
for (int i : taken_out) removed[i] = true;
for (int i : taken_in) {
move_outside(i);
in_machine.pop_back();
}
}
}
return ans;
}
