#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; }