#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
// void move_inside(int i)
// void move_outside(int i)
// int press_button()
const int TAILLEMAXI=2002;
int prenable[TAILLEMAXI];
int deja[TAILLEMAXI];
int nbgroupes;
int min_cardinality(int N) {
fill(prenable, prenable + TAILLEMAXI, 0);
fill(deja, deja + TAILLEMAXI, 0);
nbgroupes = 0;
for (int i=0;i<N;i++){
move_inside(i);
cerr << "in " << i << endl;
if (nbgroupes==0 or press_button()==1){
prenable[i]=1;
nbgroupes++;
deja[i]=1;
}
else {
move_outside(i);
cerr << "out " << i << endl;
}
}
int nbdedans=nbgroupes;
int g=1,d=N/nbgroupes;
while (g<d){
int m=(g+d+1)/2;
for (int i=0;i<N;i++){
if (prenable[i]==0 and deja[i]==0){
move_inside(i);
cerr << "in " << i << endl;
if (press_button()>m){
move_outside(i);
cerr << "out " << i << endl;
}
else {
deja[i]=1;
nbdedans++;
}
}
}
cerr << nbdedans << " " << nbgroupes << " " << m << " ";
if (nbdedans==m*nbgroupes){
cerr << "lft" << endl;
g=m;
for (int i=0;i<N;i++){
if (deja[i]==1){
prenable[i]=1;
}
}
}
else {
cerr << "rgt" << endl;
d=m-1;
for (int i=0;i<N;i++){
if (deja[i]==0) prenable[i] = 1;
}
for (int i=0;i<N;i++){
if (deja[i]==1 and prenable[i]==0){
move_outside(i);
cerr << "out " << i << endl;
deja[i]=0;
nbdedans--;
}
}
}
}
return g;
}
