Background

This is an interactive problem.

You do not need and must not include the insects.h header file or the main function in your submitted program.

However, in your program you need to declare the following three functions:

void move_inside(int i);
void move_outside(int i);
int press_button();

For example, your program can look like this:

#include <bits/stdc++.h>
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
	// Code Here
}

Background

Problem Description

There are $N$ insects around Pak Blangkon’s house, numbered from $0$ to $N - 1$. Each insect has a type, represented by an integer ID from $0$ to $10^9$ (including $0$ and $10^9$). Multiple insects may have the same type.

Suppose we group the insects by type. We define the cardinality of the most common insect type as the number of insects in the largest group. Similarly, the cardinality of the rarest insect type is the number of insects in the smallest group.

For example, suppose there are $11$ insects with types $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$. In this case, the cardinality of the most common insect type is $3$, because the groups of type $9$ and type $11$ both have the largest number of insects, and each group has $3$ insects. The cardinality of the rarest insect type is $1$, because the groups of type $7$, type $0$, and type $100$ all have the smallest number of insects, and each group has $1$ insect.

Pak Blangkon does not know the types of these insects. He has a one-button machine that can provide information about insect types. Initially, the machine is empty. When using the machine, you can perform the following three operations:

1. Put an insect into the machine.
2. Take an insect out of the machine.
3. Press the button on the machine.

Each operation can be performed at most $40\;000$ times.

Whenever the button is pressed, the machine reports the cardinality of the most common insect type currently inside the machine.

Your task is to use the machine above to determine the cardinality of the rarest insect type among all $N$ insects around Pak Blangkon’s house. Also, in some subtasks, your score depends on the maximum number of times the machine performs a certain operation (see the Subtasks section for details).

Input Format

You need to implement the following function:

int min_cardinality(int N)

• $N$: the number of insects.
• This function should return the cardinality of the rarest insect type among all $N$ insects around Pak Blangkon’s house.
• This function is called exactly once.

This function may call the following functions:

void move_inside(int i)

• $i$: the ID of the insect to be put into the machine. The value of $i$ is between $0$ and $N - 1$ (including $0$ and $N - 1$).
• If the insect is already inside the machine, the call will not change the set of insects inside the machine. However, the call is still counted toward the number of such operations.
• This function can be called at most $40\;000$ times.

void move_outside(int i)

• $i$: the ID of the insect to be taken out of the machine. The value of $i$ is between $0$ and $N - 1$ (including $0$ and $N - 1$).
• If the insect is already outside the machine, the call will not change the set of insects inside the machine. However, the call is still counted toward the number of such operations.
• This function can be called at most $40\;000$ times.

int press_button()

• This function returns the cardinality of the most common insect type inside the machine.
• This function can be called at most $40\;000$ times.
• The grader is not adaptive. That is, the types of all $N$ insects are fixed before min_cardinality is called.

Output Format

Consider a scenario where there are $6$ insects with types $[5, 8, 9, 5, 9, 9]$. The function min_cardinality is called as follows:

min_cardinality(6)

This function calls move_inside, move_outside, and press_button in the following order.

At this point, there is enough information to conclude that the cardinality of the rarest insect type is $1$. Therefore, the function min_cardinality should return $1$.

In this example, move_inside is called $7$ times, move_outside is called $1$ time, and press_button is called $6$ times.

Hint

Constraints

• $2 \le N \le 2000$.

Subtasks

1. (10 points) $N \le 200$.
2. (15 points) $N \le 1000$.
3. (75 points) no additional constraints.

If, on some test case, the number of calls to move_inside, move_outside, or press_button does not satisfy the constraints given in “Implementation details”, or the return value of min_cardinality is incorrect, then your score for that subtask is $0$.

Let $q$ be the maximum of the following three values: the number of calls to move_inside, the number of calls to move_outside, and the number of calls to press_button.

In Subtask 3, you may receive partial score. Let $m$ be the maximum value of $\frac{q}{N}$ over all test cases in this subtask. Your score for this subtask will be calculated according to the following table:

Example grader

Let $T$ be an integer array of length $N$, where $T[i]$ is the type of insect with ID $i$.

The example grader reads input in the following format:

• Line $1$: $N$.
• Line $2$: $T[0] \; T[1] \; \ldots \; T[N - 1]$.

If the example grader detects illegal behavior, it will output Protocol Violation: <MSG>, where <MSG> is one of the following:

• invalid parameter: in a call to move_inside or move_outside, the value of parameter $i$ is not in the range from $0$ to $N - 1$ (including $0$ and $N - 1$).
• too many calls: the number of calls to at least one of move_inside, move_outside, and press_button exceeds $40\;000$.

Otherwise, the example grader outputs in the following format:

• Line $1$: the return value of min_cardinality.
• Line $2$: $q$.

Notes

In the statement, the function interfaces use general type names void, bool, int, int[] (array), and union(bool, int[]).

In C++, the grader will use appropriate data types or implementations, as shown in the following tables:

In C++, std::variant is defined in the <variant> header. A function with return type std::variant<bool, std::vector<int>> can return either a bool or a std::vector<int>. The following sample code shows three functions that return a std::variant, and they all work correctly:

std::variant<bool, std::vector<int>> foo(int N) {
    return N % 2 == 0;
}

std::variant<bool, std::vector<int>> goo(int N) {
    return std::vector<int>(N, 0);
}

std::variant<bool, std::vector<int>> hoo(int N) {
    if (N % 2 == 0) {
        return false;
    }

    return std::vector<int>(N, 0);
}

Translated by ChatGPT 5