#include "insects.h"
#include<bits/stdc++.h>
#define out(x) #x <<" = "<<x<<" "
using namespace std;
int min_cardinality(int N) {
int l = 2, r = N, mid, ans = 1, diff = 1;
vector<int> ll, rr;
bool used[2010] = {}, last = true;
//bool curr_used[2010] = {};
move_inside(0);
ll.push_back(0);
used[0] = true;
for(int i = 1; i < N; i++){
move_inside(i);
if(press_button() != 1){
move_outside(i);
}else{
ll.push_back(i);
used[i] = true;
}
}
diff = ll.size();
// cout<<out(diff)<<endl;
//r = N / diff;
while(l <= r){
vector<int> curr;
mid = (l + r)/2;
//cout<<out(l)<<out(r)<<out(mid)<<endl;
for(int i = 1; i < N; i++){
if(used[i]) continue;
move_inside(i);
if(press_button() > mid){
move_outside(i);
}else{
curr.push_back(i);
}
}
if((curr.size() + ll.size()) == (diff * mid)){
ans = mid;
l = mid + 1;
ll = curr;
for(int i: curr){
used[i] = true;
}
}else{
r = mid - 1;
rr = curr;
//cout<<curr.size()<<endl;
for(int i: curr){
move_outside(i);
}
}
}
return ans;
}
