#include "insects.h"
#include <vector>
#include <algorithm>
#include <iostream>
/*std::vector<int> types(0);
std::vector<int> inside(0);
int maximal_type = 0;
void move_inside(int i) {
inside.push_back(i);
}
void move_outside(int i) {
for (int j = 0; j < inside.size(); j++) {
if (inside[j] == i) {
inside.erase(inside.begin() + j);
break;
}
}
}
int press_button() {
std::vector<int> values(maximal_type + 1);
int max_res = 0;
for (int i = 0; i < inside.size(); i++) {
values[types[i]] += 1;
if (values[types[i]] > max_res) {
max_res = values[types[i]];
}
}
return max_res;
}//*/
std::vector<bool> visited(0);
void init(int N) {
visited.resize(N, false);
}
int get_number_of_types(int N) {
move_inside(0);
int counter = 1;
visited[0] = true;
for (int i = 1; i < N; i++) {
move_inside(i);
int value = press_button();
if (value == 1) {
visited[i] = true;
counter += 1;
}
else {
move_outside(i);
}
}
return counter;
}
void remove_all_indexes(std::vector<int> indexes) {
for (int i = 0; i < int(indexes.size()); i++) {
move_outside(indexes[i]);
}
}
int first_solution(int N) {
int number_of_types = get_number_of_types(N);
int current_result = 1;
std::vector<int> inside_indexes(0);
bool any_change = true;
while (any_change) {
any_change = false;
for (int i = 0; i < N; i++) {
if (visited[i]) {
continue;
}
move_inside(i);
int value = press_button();
if (value > current_result + 1) {
move_outside(i);
}
else {
visited[i] = true;
inside_indexes.push_back(i);
}
if (int(inside_indexes.size()) == number_of_types) {
any_change = true;
remove_all_indexes(inside_indexes);
}
}
remove_all_indexes(inside_indexes);
inside_indexes.resize(0);
}
return current_result;
}
int min_cardinality(int N) {
init(N);
return first_solution(N);
}
/*int main() {
// 5, 8, 9,5 ,9 ,9
maximal_type = 9;
types = { 5 ,8 ,9 ,5 , 9,9 };
std::cout << min_cardinality(6);
}//*/
