#include "insects.h"
#include <vector>
int min_cardinality(int n) {
int distincte, i, st, dr, mij, cnt, answer;
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;
answer = 1;
st = 2;
dr = n / distincte;
while(st <= dr) {
mij = (st + dr) / 2;
new_in = new_out = {};
for(i = 0; i < (int)out.size(); i++) {
if(cnt == distincte * mij) {
// De acum incolo clar o sa fiu doar in cazul in care scot pe out[i]
new_out.push_back(out[i]);
} else {
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 + 1;
answer = mij;
// Pe cele din new_in o sa le lasam inauntru mereu
out = new_out;
} else {
dr = mij - 1;
// 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 answer;
}
