#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 inside.size();
}
bool test(int k) //Every type at least k insects?
{
while(press_button() > k)
{
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((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();
if(types <= 7)
{
while(inside.size())
{
move_outside(*inside.begin());
outside.insert(*inside.begin());
inside.erase(inside.begin());
}
vector<int> card(N, -1);
for(int i = 0; i < N; i++)
{
if(card[i] == -1)
{
move_inside(i);
vector<int> machine = {i};
for(int j = i+1; j < N; j++)
{
if(card[j] == -1)
{
move_inside(j);
machine.push_back(j);
int state = press_button();
if(state != (int) machine.size())
{
move_outside(j);
machine.pop_back();
}
}
}
for(int j : machine)
{
card[j] = machine.size();
move_outside(j);
}
}
}
return *min_element(card.begin(), card.end());
}
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;
}
