#include <bits/stdc++.h> #include "insects.h" using namespace std; deque <int> PrevIndex; int InMachine[2003]; int n; int TypeCount; int PossibleMincount(int cnt){ PrevIndex.clear(); //Pushing insects inside the machine, keeping track of the ones being putted inside for this iteration of binary searching for(int i=0;i<n;i++){ if(!InMachine[i]){ InMachine[i]=1; move_inside(i); PrevIndex.push_back(i); if(press_button()>cnt){ move_outside(i); InMachine[i]=0; PrevIndex.pop_back(); } } } int CurrentInMachine=0; for(int i=0;i<n;i++){ CurrentInMachine+=InMachine[i]; } if(CurrentInMachine<cnt*TypeCount){ //There clearly exist a type of insect with cardinality less than cnt, so the answer is less than cnt. Removing insects from last iteration. while(!PrevIndex.empty()){ InMachine[PrevIndex.front()]=0; move_outside(PrevIndex.front()); PrevIndex.pop_front(); } return 0; }else{ //As every type of insects has at least cnt insects, the answer is at least cnt. Just return true PrevIndex.clear(); return 1; } } int min_cardinality(int N){ int l,r,mid; n=N; l=1; //Phase 1: Determining the amount of different types of insects for(int i=0;i<n;i++){ move_inside(i); InMachine[i]=1; PrevIndex.push_back(i); if(press_button()>1){ move_outside(i); InMachine[i]=0; PrevIndex.pop_back(); } } TypeCount=PrevIndex.size(); r=N/TypeCount+1; //Remember to empty the machine before actually binary searching as well. Silly me while(!PrevIndex.empty()){ InMachine[PrevIndex.front()]=0; move_outside(PrevIndex.front()); PrevIndex.pop_front(); } //Phase 2: Binary search for the answer while(r-l>=1){ mid=(l+r)/2; if(PossibleMincount(mid)){ l=mid; }else{ r=mid-1; } } if(PossibleMincount(l)){ return l; }else{ return r; } }