#include "insects.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include <iostream>
std::mt19937 rng(123);
int min_cardinality(int n) {
std::vector<int> reprezentant;
std::vector<int> order(n);
for (int i = 0; i < n; i++) {
order[i] = i;
}
std::shuffle(order.begin(), order.end(), rng);
for (int i : order) {
move_inside(i);
if (press_button() >= 2) {
move_outside(i);
} else {
reprezentant.push_back(i);
}
}
std::vector<bool> taken(n, false);
if ((int) reprezentant.size() > n / 2) {
return 1;
}
int mini = n;
for (int i : reprezentant) {
taken[i] = true;
int me = 1; // doar pe i
move_inside(i);
for (int x : order) {
if (me >= mini) {
break;
}
if (!taken[x]) {
move_inside(x);
if (press_button() == 2) {
taken[x] = true;
me++;
}
move_outside(x);
}
}
move_outside(i);
mini = std::min(mini, me);
}
return mini;
}
