#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
set<int> inside;
set<int> outside;
int types = -1;
int countTypes()
{
while(inside.size() && press_button() > 1)
{
move_outside(*inside.begin());
outside.insert(*inside.begin());
inside.erase(inside.begin());
}
vector<int> a(0);
for(int i : outside)
{
a.push_back(i);
}
for(int i : a)
{
move_inside(i);
inside.insert(i);
outside.erase(i);
if(inside.size() > 1)
{
if(press_button() > 1)
{
move_outside(i);
outside.insert(i);
inside.erase(i);
}
}
}
return outside.size();
}
bool test(int k) //Every type at least k insects?
{
while(press_button() > k)
{
move_outside(*outside.begin());
outside.erase(outside.begin());
}
vector<int> a(0);
for(int i : outside)
{
a.push_back(i);
}
for(int i : a)
{
move_inside(i);
inside.insert(i);
outside.erase(i);
if((int) inside.size() > k)
{
if(press_button() > k)
{
move_outside(i);
outside.insert(i);
inside.erase(i);
}
}
}
return((int) inside.size() == k*types);
}
int min_cardinality(int N)
{
for(int i = 0; i < N; i++)
{
outside.insert(i);
}
types = countTypes();
int left = 1;
int right = N/types;
while(left < right)
{
int mid = (left+right+1)/2;
if(test(mid))
{
left = mid;
}
else
{
right = mid-1;
}
}
return left;
}
