#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
bool in[2005],bad[2005];
mt19937 rng(218);
int min_cardinality(int N){
int types=0;
for(int i=0;i<N;++i){
move_inside(i);
in[i]=true;
if(press_button()>1){
move_outside(i);
in[i]=false;
}
else ++types;
}
int lo=2,hi=N/types,mid,res=1;
vector<int> add;
int tot=types;
vector<int> index;
for(int i=0;i<N;++i){
index.push_back(i);
}
while(lo<=hi){
mid=(lo+hi)>>1;
add.clear();
vector<int> newbad;
shuffle(index.begin(),index.end(),rng);
for(int i:index){
if(in[i]||bad[i])continue;
move_inside(i);
in[i]=true;
++tot;
if(press_button()>mid){
move_outside(i);
in[i]=false;
newbad.push_back(i);
--tot;
}
else add.push_back(i);
if(tot==mid*types)break;
}
if(tot==mid*types){
res=mid;
lo=mid+1;
}
else{
hi=min(mid-1,tot/types);
for(int i:add){
move_outside(i);
in[i]=false;
--tot;
}
for(int i:newbad){
bad[i]=true;
}
}
}
return res;
}
