#include "insects.h"
#include <vector>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
pair<vector<int>, int> check(vector<int> vc, int tst)
{
vector<bool> u(vc.size());
vector<int> toremove;
for (int i = 0; i < (int)vc.size(); i++) {
move_inside(vc[i]);
if (press_button() > tst) {
move_outside(vc[i]);
u[i] = true;
}
else toremove.push_back(vc[i]);
}
for (int i:toremove) move_outside(i);
toremove.clear();
int cnt = 0;
for (int i = 0; i < (int)vc.size(); i++) {
if (!u[i]) continue;
move_inside(vc[i]);
if (press_button() > 1) {
move_outside(vc[i]);
}
else {
toremove.push_back(vc[i]);
cnt++;
}
}
for (int i = 0; i < (int)vc.size(); i++) {
if (u[i]) continue;
move_inside(vc[i]);
if (press_button() > 1) u[i] = true;
move_outside(vc[i]);
}
for (int i:toremove) move_outside(i);
vector<int> nxt;
for (int i = 0; i < (int)vc.size(); i++) {
if (!u[i]) nxt.push_back(vc[i]);
}
return make_pair(nxt, cnt);
}
int random(int l, int r)
{
return rand() % (r - l + 1) + l;
}
int get_min(vector<int> vc, int spec)
{
if (spec == 1) return vc.size();
int mx = vc.size() / spec;
int mi = 1;
while (1) {
int tst = random(mi, mx);
auto [v, k] = check(vc, tst);
if (v.size() == vc.size()) return mx;
if (v.size() == 0) mi = tst + 1;
else return get_min(v, spec - k);
}
}
int min_cardinality(int N) {
srand(time(NULL));
vector<int> vc;
for (int i = 0; i < N; i++) vc.push_back(i);
int cnt = 0;
vector<int> toremove;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() >= 2) {
move_outside(i);
}
else {
toremove.push_back(i);
cnt++;
}
}
for (int i:toremove) move_outside(i);
return get_min(vc, cnt);
}
