#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int min_cardinality(int N) {
int cnt=0;
set<int> in;
vector<int> ids;
for(int i=0;i<N;i++){
ids.push_back(i);
move_inside(i);
int x=press_button();
if(x>1)move_outside(i);
else{
cnt++;
in.insert(i);
}
}
if(cnt==1)return N;
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(ids.begin(), ids.end(), g);
int l=N/cnt;
while(l>1){
vector<int> nw;
for(int id=0;id<N;id++){
int i=ids[id];
if(in.size()==l*cnt || in.find(i)!=in.end())continue;
move_inside(i);
int x=press_button();
if(x>l)move_outside(i);
else{
in.insert(i);
nw.push_back(i);
}
}
if(in.size()==l*cnt)return l;
else{
ids.clear();
for(auto i:in)ids.push_back(i);
std::shuffle(ids.begin(), ids.end(), g);
N=(int)ids.size();
for(auto i:nw){
move_outside(i);
in.erase(i);
}
l=N/cnt;
}
}
return l;
}
