#include "insects.h"
#include <vector>
int min_cardinality(int n) {
int distincte, i, st, dr, mij, cnt;
std::vector<int> out, new_in, new_out;
distincte = 0;
for(i = 0; i < n; i++) {
move_inside(i);
if(press_button() == 1) {
distincte++;
} else {
move_outside(i);
out.push_back(i);
}
}
cnt = distincte;
st = 1;
dr = n / distincte + 1;
while(dr - st > 1) {
mij = (st + dr) / 2;
new_in = new_out = {};
cnt = 0;
for(i = 0; i < (int)out.size(); i++) {
move_inside(out[i]);
if(press_button() == mij + 1) {
move_outside(out[i]);
new_out.push_back(out[i]);
} else {
cnt++;
new_in.push_back(out[i]);
}
}
if(cnt == distincte * mij) {
st = mij;
// Pe cele din new_in o sa le lasam inauntru mereu
out = new_out;
} else {
dr = mij;
// Pe cele din new_out nu o sa le mai folosim niciodata
for(i = 0; i < (int)new_in.size(); i++) {
cnt--;
move_outside(new_in[i]);
}
out = new_in;
}
}
return st;
}
