#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int min_cardinality(int N) {
bitset<2000> inside;
int nbElems = 0;
for (int i=0; i<N; ++i){
move_inside(i);
if (i != 0){
int maxFreq = press_button();
if (maxFreq > 1) move_outside(i);
else{
++nbElems;
inside[i] = true;
}
}
else{
++nbElems;
inside[i] = true;
}
}
if (nbElems == 1) return N;
if (nbElems == N) return 1;
int in = nbElems, crt = 1;
int deb = 2, fin = N/nbElems, ans = 1;
vector<int> last;
while (deb <= fin){
int mid = (deb+fin)/2;
bool ok = false;
if (crt > mid){
for (int i:last){
inside[i] = false;
in--;
move_outside(i);
}
}
last.clear();
vector<int> outside;
for (int i=0; i<N; ++i){
if (!inside[i]){
move_inside(i);
++in;
crt = press_button();
if (in == mid*nbElems and crt == mid){
ok = true;
inside[i] = true;
last.emplace_back(i);
break;
}
if (crt > mid){
outside.emplace_back(i);
move_outside(i);
--in;
}
else{
inside[i] = true;
last.emplace_back(i);
}
}
}
if (ok){
crt = mid;
ans = mid;
deb = mid+1;
}
else{
for (int i:outside) inside[i] = true;
fin = mid-1;
}
crt = mid;
}
return ans;
}
