#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int tailleCard(int N, vector<bool>& used) {
int taille = 0;
vector<int> list;
for (int i = 0; i < N; i++) {
if (!used[i]) {
move_inside(i);
if (press_button() != 1) {
move_outside(i);
}
else {
used[i] = true;
taille++;
list.push_back(i);
}
}
}
for (int i : list) move_outside(i);
return taille;
}
int eliminate(int N, vector<bool>& used) {
vector<int> list;
for (int i = 0; i < N; i++) {
if (!used[i]) {
move_inside(i);
}
}
int cardMax = press_button();
for (int i = 0; i < N; i++) {
if (!used[i]) {
move_outside(i);
if (press_button() < cardMax) {
move_inside(i);
used[i] = true;
list.push_back(i);
}
}
}
for (int i : list) move_outside(i);
return cardMax;
}
int min_cardinality(int N) {
vector<bool> used(N);
int last = tailleCard(N, used);
int nbRestants = N-last;
int nbOperations = 1;
int cardAct = (nbRestants+last-1)/last;
while (nbRestants > 0) {
if (cardAct > last) {
int result = eliminate(N, used);
nbRestants -= result;
last--;
cardAct = (nbRestants+last-1)/(last);
if (nbRestants == 0) {
return result + nbOperations;
}
}
else {
int another = tailleCard(N, used);
if (another != last) return nbOperations;
nbOperations++;
last = another;
nbRestants -= last;
cardAct = (nbRestants+last-1)/last;
}
}
return nbOperations;
}
