#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
const int N = 2e3 + 10 , Lg = 10;
int n , ans , cnt;
bool bad[N] , dead[N];
bool check(int mid)
{
//cout << "Check : " << mid << endl;
int all_in = 0;
for(int i = 0 ; i < n ; i++) if(!dead[i])
{
bad[i] = false;
all_in++;
move_inside(i);
int val = press_button();
if(val > mid)
{
bad[i] = true;
all_in--;
move_outside(i);
}
}
//cout << mid << " : " << all_in << endl;
for(int i = 0 ; i < n ; i++) if(!bad[i] && !dead[i])
move_outside(i);
if(all_in == cnt * mid)
{
for(int i = 0 ; i < n ; i++) if(!dead[i] && !bad[i])
dead[i] = true;
return true;
}
else
{
for(int i = 0 ; i < n ; i++) if(!dead[i] && bad[i])
dead[i] = true;
return false;
}
}
int min_cardinality(int nn)
{
n = nn;
vector <int> vec;
for(int i = 0 ; i < n ; i++)
{
move_inside(i);
int val = press_button();
if(val == 1)
{
cnt++;
vec.push_back(i);
}
else
{
move_outside(i);
}
}
for(auto u : vec)
move_outside(u);
//cout << cnt << endl;
int mx = n / cnt + 1;
while(mx > 1)
{
int mid = mx / 2;
//cout << mx << " : " << mid << endl;
if(check(mid))
{
mx = mx - mid;
ans += mid;
}
else
{
mx = mid;
}
}
return ans;
}
