#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
vector<int> temp;
int d = 0;
for (int i = 0; i < N; i++){
move_inside(i);
int count = press_button();
if (count > 1){
move_outside(i);
}
else{
temp.push_back(i);
d++;
}
}
for (int i = 0; i < temp.size(); i++){
move_outside(temp[i]);
}
int ans = N;
int oriN = N;
vector<int> newUse(N);
for (int i = 0; i < N; i++){
newUse[i] = i;
}
if (d == 1) return N;
if (N / d <= 10){
while(1){
int B = N / d;
vector<int> all;
for (int i = 0; i < newUse.size(); i++){
move_inside(newUse[i]);
int count = press_button();
if (count > B){
move_outside(newUse[i]);
}
else{
all.push_back(newUse[i]);
if (all.size() == B * d) break;
}
}
if (all.size() == B * d){
return B;
}
N = all.size();
for (int i = 0; i < all.size(); i++){
move_outside(all[i]);
}
newUse = all;
}
}
else{
int ans = N;
int l = 1, r = N / d, mid;
while(l <= r){
mid = (r - l) / 2 + l;
vector<int> allIn;
for (int i = 0; i < N; i++){
move_inside(i);
int count = press_button();
if (count > mid){
move_outside(i);
}
else{
allIn.push_back(i);
if (allIn.size() == d * mid) break;
}
}
if (allIn.size() == d * mid){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
for (int i = 0; i < allIn.size(); i++){
move_outside(allIn[i]);
}
}
return ans;
}
return 1;
}
