#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
int low = 1;
int high = N;
int nG = 0;
map<int, bool> isIn;
for(int i = 0; i < N; i++){
move_inside(i);
isIn[i] = true;
int ret = press_button();
if(ret == 2){
isIn[i] = false;
move_outside(i);
}else
nG++;
}
for(int i = 0; i < N; i++) if(isIn[i]) {move_outside(i); isIn[i]=false;}
while(low <= high){
int mid = low + (high-low)/2;
// man mano che arrivo al borderline (mid) mi salvo qualcosa, l'ultimo inserito
// e conto il numero di borderline
// se il numero di borderline è uguale al numero di gruppi, allora
// o la risposta è mid, oppure tutti questi superano il borderline
// altrimenti scendo mid
int cnt = 0, cnt1 = 0;
for(int i = 0; i < N; i++){
move_inside(i);
isIn[i] = true;
int ret = press_button();
if(ret == mid) cnt++;
if(ret == mid+1){
isIn[i] = false;
move_outside(i);
cnt1++;
}
}
// cout<<"DEBUG-->"<<mid<<" "<<(N-cnt1)<<" "<<cnt1<<endl;
if(cnt1 + mid * nG == N) low = mid+1;
else high = mid-1;
// devo cacciare quelli rimasti
for(int i = 0; i < N; i++) if(isIn[i]) {move_outside(i); isIn[i]=false;}
}
return low-1;
}
