#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
deque<int> act, nex, in;
int getMin(int nbType) {
int n = act.size();
if(nbType == 1)
return n;
if(nbType > n)
return 0;
int del = (int)ceil(0.45 * (double)n / (double)nbType);
for(int i = 0; i < n; i++) {
move_inside(act[i]);
if(press_button() == del+1) {
move_outside(act[i]);
nex.push_back(act[i]);
} else {
in.push_back(act[i]);
}
}
if((int)in.size() == del * nbType) {
swap(act, nex);
for(int i : in)
move_outside(i);
in.clear();
nex.clear();
return del + getMin(nbType);
}
for(int i : in)
move_outside(i);
deque<int> repr, garde;
for(int i : nex) {
move_inside(i);
if(press_button() == 1) {
repr.push_back(i);
} else {
move_outside(i);
}
}
for(int i : in) {
move_inside(i);
if(press_button() == 1) {
garde.push_back(i);
}
move_outside(i);
}
for(int i : repr)
move_outside(i);
swap(garde, act);
garde.clear();
nex.clear();
in.clear();
return getMin(nbType - (int)repr.size());
}
int min_cardinality(int N) {
int nbType = 0;
for(int i = 0; i < N; i++)
act.push_back(i);
for(int i = 0; i < N; i++) {
move_inside(i);
if(press_button() == 2) {
move_outside(i);
nex.push_back(i);
} else {
nbType++;
in.push_back(i);
}
}
for(int i : in)
move_outside(i);
swap(act, nex);
nex.clear();
in.clear();
return getMin(nbType) + 1;
}
