Description

Mushroom expert Andrew is studying local mushrooms in Singapore.

As part of the study, Andrew collected $n$ mushrooms, numbered from $0$ to $n-1$. Each mushroom belongs to one of two species, called $A$ or $B$.

Andrew knows that mushroom $0$ belongs to species $A$, but since the two species look very similar, he does not know whether mushrooms $1$ to $n-1$ are $A$ or $B$.

Fortunately, Andrew has a machine in his lab that can help. To use the machine, you put two or more mushrooms into the machine and arrange them in a line (in any order), then turn on the machine. The machine will compute the number of adjacent pairs of mushrooms that are not of the same species. For example, if you put mushrooms of species $\left[A, B, B, A\right]$ (in this order) into the machine, the result should be $2$.

However, because operating the machine is very expensive, it can only be used a limited number of times. Moreover, across all uses of the machine, the total number of mushrooms placed into the machine cannot exceed $10^5$. Use this machine to help Andrew count how many mushrooms of species $A$ he collected.

Implementation details

You need to implement the following function:

int count_mushrooms(int n)

• n: the number of mushrooms Andrew collected.
• This function will be called exactly once, and it should return the number of mushrooms of species $A$.

The above function may call the following function:

int use_machine(vector<int> x)

• x: an array of length between $2$ and $n$ (inclusive), giving in order the indices of the mushrooms placed into the machine.
• The elements of x must be distinct integers between $0$ and $n-1$ (inclusive).
• Suppose the length of x is $d$. Then this function returns the number of indices $j$ such that $0 \le j \le d-2$ and $x[j]$ and $x[j+1]$ belong to different species.
• This function can be called at most $2 \times 10^4$ times.
• Across all calls to use_machine, the sum of the lengths of all arrays $x$ passed to use_machine must not exceed $10^5$.

Hint

Sample explanation

Example 1

Consider the following scenario: there are $3$ mushrooms, with species in order $\left[A,B,B\right]$. The function count_mushrooms is called in the following way:

count_mushrooms(3)

This function can call use_machine([0, 1, 2]), which in this scenario returns $1$. The function then calls use_machine([2, 1]), which returns $0$.

At this point, there is enough information to conclude that there is only $1$ mushroom of species $A$. Therefore, count_mushrooms should return $1$.

Example 2

Consider the following example: there are $4$ mushrooms, with species in order $\left[A,B,A,A\right]$. The function count_mushrooms is called as follows:

count_mushrooms(4)

This function can call use_machine([0, 2, 1, 3]), which returns $2$. It then calls use_machine([1,2]), which returns $1$.

At this point, there is enough information to conclude that there are $3$ mushrooms of species $A$. Therefore, count_mushrooms should return $3$.

Constraints

• $2 \le n \le 2 \times 10^4$

Scoring

For all test cases, if your calls to use_machine do not satisfy the requirements described above, or if the return value of count_mushrooms is not correct, your score will be $0$. Otherwise, let $Q$ be the maximum number of calls to use_machine among all test cases. Then your score will be computed according to the following table:

On some test cases, the behavior of the grader is adaptive. That is, in these test cases, the grader does not have a fixed sequence of mushroom species. Instead, the answers given by the grader may depend on previous calls to use_machine.

However, it is guaranteed that the answers given by the grader satisfy the following: after each interaction, there exists at least one sequence of mushroom species that is consistent with all answers given so far.

Example grader

The example grader reads an integer array $s$, which gives the species of the mushrooms. For all $0 \le i \le n-1$, $s[i]=0$ means mushroom $i$ is of species $A$, and $s[i]=1$ means mushroom $i$ is of species $B$. The example grader reads input in the following format:

Line $1$: $n$
Line $2$: $s[0]\ s[1]\ \ldots\ s[n-1]$

The output of the example grader is in the following format:

Line $1$: the return value of count_mushrooms.
Line $2$: the number of calls to use_machine.

Note that the example grader is not adaptive.

Translated by ChatGPT 5