#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int nbInside = 0;
vector<bool> in, alive;
void inside(int i) {
if(in[i]) return;
in[i] = true;
move_inside(i);
nbInside++;
}
void outside(int i) {
if(!in[i]) return;
in[i] = false;
move_outside(i);
nbInside--;
}
int getNbType(int N) {
int nb = 0;
for(int i = 0; i < N; i++)
if(alive[i]) {
nb++;
inside(i);
if(press_button() == 2) {
nb--;
outside(i);
}
}
for(int i = 0; i < N; i++)
outside(i);
return nb;
}
int min_cardinality(int n) {
in.resize(n);
alive.resize(n);
int nbAlive = n;
for(int i = 0; i < n; i++) alive[i] = true;
int nbType = getNbType(n),
majorant = 1000*1000, suppr = 0;
while(majorant * nbType > nbAlive) {
int test = (int)ceil((0.5 * nbAlive) / nbType);
for(int i = 0; i < n; i++)
if(alive[i]) {
inside(i);
if(press_button() > test)
outside(i);
}
if(nbInside == nbType * test) {
suppr += test;
majorant -= test;
for(int i = 0; i < n; i++)
if(in[i]) {
alive[i] = false;
nbAlive--;
}
for(int i = 0; i < n; i++)
outside(i);
if(nbType > getNbType(n))
majorant = 0;
} else {
majorant = test;
for(int i = 0; i < n; i++)
if(!in[i] && alive[i]) {
alive[i] = false;
nbAlive--;
}
for(int i = 0; i < n; i++)
outside(i);
}
}
if(nbAlive == 0) majorant = 0;
return majorant + suppr;
}
