#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int const sz=2000;
bitset<sz>ind,ind1,ver[sz];
int pre;
bool chn;
int ask()
{
if (chn==0)
return pre;
pre=press_button();
chn=0;
return pre;
}
// int ran(int j)
// {
// return rand()%j;
// }
int min_cardinality(int N)
{
srand(time(0));
int colors=0;
vector<int>inds;
for (int i=0;i<N;i++)
inds.push_back(i);
mt19937 mt(783242309);
shuffle(inds.begin(),inds.end(),mt);
for (int i=0;i<N;i++)
{
ind[inds[i]]=1;
chn=1;
move_inside(inds[i]);
colors++;
if (ask()>1)
{
ind[inds[i]]=0;
chn=1;
move_outside(inds[i]);
colors--;
}
}
ver[1]=ind;
set<int>s;
s.insert(1);
for (int i=0;i<N;i++)
ind1[i]=1-ind[i];
int cnt=colors;
int st=1,en=N/colors+1;
while (st+1<en)
{
int mid=(st+en)/2;
auto z=s.lower_bound(mid);
z--;
int pre=*z;
for (int i=0;i<N;i++)
{
if (ver[pre][inds[i]]==ind[inds[i]]) continue;
if (ver[pre][inds[i]])
{
chn=1;
move_inside(inds[i]);
ind[inds[i]]=1;
ind1[inds[i]]=0;
cnt++;
}
else
{
chn=1;
move_outside(inds[i]);
ind[inds[i]]=0;
ind1[inds[i]]=1;
cnt--;
}
}
for (int i=0;i<N;i++)
{
if (cnt==colors*mid)
break;
if (ind1[inds[i]])
{
chn=1;
move_inside(inds[i]);
ind[inds[i]]=1;
cnt++;
if (ask()>mid)
{
cnt--;
chn=1;
move_outside(inds[i]);
ind[inds[i]]=0;
}
}
}
if (cnt==colors*mid)
{
st=mid;
if (st+1>=en)
break;
for (int i=0;i<N;i++)
{
if (ind[inds[i]])
ind1[inds[i]]=0;
}
}
else
{
en=mid;
if (st+1>=en)
break;
for (int i=0;i<N;i++)
{
if (ind[inds[i]])
continue;
else
ind1[inds[i]]=0;
}
}
s.insert(mid);
ver[mid]=ind;
}
return st;
}
