#include "insects.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
vector<int>vec;
vector<int>rez;
int diff=0;
int v[2005];
int fre2[2005];
int n;
void makevecdiff()
{
for(int i=0;i<n;i++)
{
fre2[i]=0;
}
for(int i=0;i<vec.size();i++)
{
fre2[vec[i]]=1;
}
for(int i=0;i<rez.size();i++)
{
fre2[rez[i]]=0;
move_outside(rez[i]);
}
vec.clear();
rez.clear();
for(int i=0;i<n;i++)
{
if(fre2[i]==1)
{
vec.push_back(i);
}
}
}
void veceqrasp()
{
vec.clear();
for(int i=0;i<rez.size();i++)
{
move_outside(rez[i]);
vec.push_back(rez[i]);
}
rez.clear();
}
void makerez(int mij)
{
for(int i=0;i<vec.size();i++)
{
move_inside(vec[i]);
rez.push_back(vec[i]);
if(press_button()>mij)
{
move_outside(vec[i]);
rez.pop_back();
}
}
}
int min_cardinality(int N)
{
n=N;
int know=0;
for(int i=0;i<N;i++)
{
vec.push_back(i);
}
for(int i=0;i<N;i++)
{
move_inside(i);
know++;
rez.push_back(i);
if(press_button()==2)
{
move_outside(i);
know--;
rez.pop_back();
}
}
makevecdiff();
int rasp=1;
int dr=N/know-1;
while(dr)
{
if(vec.size()<know)
{
break;
}
rez.clear();
int mij=max(1,dr/3);
makerez(mij);
if(rez.size()==know*mij)
{
rasp=rasp+mij;
dr=dr-mij;
makevecdiff();
}
else
{
dr=rez.size()/know;
veceqrasp();
}
}
return rasp;
}
