#include "insects.h"

#include <numeric>
#include <vector>

int min_cardinality(int n) {
    std::vector<int> vec;
    for (int i = 0; i < n; i++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            vec.push_back(i);
        }
    }
    int d = vec.size();
    for (int i : vec) {
        move_outside(i);
    }

    int b = n / d;

    std::vector<int> all(n);
    std::iota(all.begin(), all.end(), 0);

    while (true) {
        std::vector<int> vec;
        for (int i : all) {
            move_inside(i);
            if (press_button() > b) {
                move_outside(i);
            } else {
                vec.push_back(i);
            }
        }
        for (int i : vec) {
            move_outside(i);
        }
        if (vec.size() == d * b) {
            break;
        } else {
            b = vec.size() / d;
            all = vec;
        }
    }

    return b;
}