#include "insects.h"
#include <iostream>
#include <vector>
using namespace std;
// <|°_°|>
// JeanBombeur & M. Broccoli
// The hardest choices require the strongest wills
// What is better - to be born good, or to overcome your evil nature with great effort ?
const int MAX_INSECTS = (2000);
vector <int> Alive;
vector <int> In;
vector <int> Out;
int nbTypes = 0;
int nbInsects;
int Check() {
int sz = Alive.size();
int value = (sz / nbTypes + 1) / 2;
// int value = (sz + 2 * nbTypes - 1) / (2 * nbTypes);
In.clear();
Out.clear();
for (int a : Alive)
{
move_inside(a);
if (press_button() > value)
move_outside(a), Out.push_back(a);
else
In.push_back(a);
}
for (int a : In)
move_outside(a);
if ((int)In.size() == value * nbTypes)
{
Alive = Out;
return value;
}
Alive = In;
return 0;
}
int min_cardinality(int N) {
nbInsects = N;
int ans = 1;
for (int i = 0; i < nbInsects; i ++)
{
move_inside(i);
if (press_button() > 1)
move_outside(i), Alive.push_back(i);
else
nbTypes ++, In.push_back(i);
}
for (int a : In)
move_outside(a);
while ((int)Alive.size() >= nbTypes)
ans += Check();
return ans;
}
