#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int AJOUTER = 0;
int RETIRER = 1;
bool superiorK(int k, int nbTypes, vector<bool>& ensemble, int N, int taille, vector<bool>& elements) {
vector<int> objets;
vector<int> oublies;
for (int i = 0; i < N; i++) {
if (!ensemble[i]) {
if (!elements[i]) {
move_inside(i);
elements[i] = true;
}
if (press_button() > (k+1)) {
if (elements[i]) {
move_outside(i);
elements[i] = false;
}
oublies.push_back(i);
elements[i] = false;
}
else {
ensemble[i] = true;
objets.push_back(i);
taille++;
}
}
}
if (taille < k*nbTypes) {
for (int i : objets) {
if (elements[i]) {
move_outside(i);
elements[i] = false;
}
ensemble[i] = false;
}
for (int i : oublies) ensemble[i] = true;
return false;
}
return true;
}
int min_cardinality(int N) {
vector<bool> ensemble(N, false);
vector<bool> elements(N, false);
int nbTypes = 0;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() != 1) {
move_outside(i);
}
else {
nbTypes++;
elements[i] = true;
}
}
int debut = 0, fin = ((N+nbTypes-1)/nbTypes);
int taille = 0;
while (debut < fin) {
int mid = (debut+fin)/2;
if (debut == mid) break;
if (superiorK(mid, nbTypes, ensemble, N, taille, elements)) {
taille = mid*nbTypes;
debut = mid+1;
}
else {
fin = mid;
}
}
if (debut != fin && superiorK(debut+1, nbTypes, ensemble, N, taille, elements)) return debut+1;
return debut;
}
