#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int par[maxn], rnk[maxn];
int used[maxn], diff, n;
vector < int > safe;
bool check(int x)
{
int cnt = safe.size();
vector < int > vec;
for (int i = 0; i < n; i ++)
{
if (!used[i])
continue;
move_inside(i);
vec.push_back(i);
if (press_button() > x)
{
move_outside(i);
vec.pop_back();
}
else
{
cnt ++;
}
}
if (cnt != x * diff)
{
for (int i = 0; i < n; i ++)
used[i] = 0;
for (int v : vec)
used[v] = 1;
for (int v : vec)
move_outside(v);
}
else
{
safe = vec;
for (int v : vec)
used[v] = 0;
}
return cnt == x * diff;
}
int find_different(int N)
{
int cnt = 0;
vector < int > vec;
for (int i = 0; i < n; i ++)
{
move_inside(i);
vec.push_back(i);
if (press_button() > 1)
{
move_outside(i);
vec.pop_back();
}
else
{
cnt ++;
}
}
for (int v : vec)
move_outside(v);
return cnt;
}
int min_cardinality(int N)
{
n = N;
diff = find_different(N);
for (int i = 0; i < N; i ++)
used[i] = 1;
int lf = 0, rf = N;
rf = N / diff;
if (diff == 1)
return N;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (check(mf))
lf = mf + 1;
else
rf = mf - 1;
}
return rf;
}
