Counting Mushrooms (mushrooms)

Andrew the mushroom expert is investigating mushrooms native to Singapore.

As part of his research, Andrew collected n mushrooms labelled 0 to n - 1. Each mushroom is of one of two species, which are called A and B.

Andrew knows that mushroom 0 belongs to species A, but as the two species look the same, he does not know the species of mushrooms 1 to n - 1.

Fortunately, Andrew has a machine in his lab that can help with this. To use this machine, one should place two or more mushrooms in a row inside the machine (in any order) and turn the machine on. Then, the machine calculates the number of adjacent pairs of mushrooms that are of different species. For example, if you place mushrooms of species [A, B, B, A] (in that order) into the machine, the result will be 2.

However, as operating the machine is very expensive, the machine can be used for a limited number of times. In addition, the total number of mushrooms placed in the machine across all its uses cannot exceed 100 000. Use this machine to help Andrew count the number of mushrooms of species A collected.

Implementation details

You should implement the following procedure:

int count_mushrooms(int n)

• n: number of mushrooms collected by Andrew.
• This procedure is called exactly once, and should return the number of mushrooms of species A.

The above procedure can make calls to the following procedure:

int use_machine(int[] x)

• x: an array of length between 2 and n inclusive, describing the labels of the mushrooms placed in the machine, in order.
• The elements of x must be distinct integers from 0 to n - 1 inclusive.
• Let d be the length of array x. Then, the procedure returns the number of different indices j, such that 0 ≤ j ≤ d - 2 and mushrooms x[j] and x[j + 1] are of different species.
• This procedure can be called at most 20 000 times.
• The total length of x passed to the procedure use_machine among all its invocations cannot exceed 100 000.

Examples

Example 1

Consider a scenario in which there are 3 mushrooms of species [A, B, B], in order. The procedure count_mushrooms is called in the following way:

count_mushrooms(3)

This procedure may call use_machine([0, 1, 2]), which (in this scenario) returns 1. It may then call use_machine([2, 1]), which returns 0.

At this point, there is sufficient information to conclude that there is only 1 mushroom of species A. So, the procedure count_mushrooms should return 1.

Example 2

Consider a case in which there are 4 mushrooms with species [A, B, A, A], in order. The procedure count_mushrooms is called as below:

count_mushrooms(4)

This procedure may call use_machine([0, 2, 1, 3]), which returns 2. It may then call use_machine([1, 2]), which returns 1.

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

Constraints

Do note that you DO NOT necessarily have to solve for the general case, but only for the subproblem defined by the following constraints:
You only need to solve for very simple cases, such as those in the examples shown.

Scoring

If in any of the test cases, the calls to the procedure use_machine do not conform to the rules mentioned above, or the return value of count_mushrooms is incorrect, the score of your solution will be 0. Otherwise, let Q be the maximum number of calls to the procedure use_machine among all test cases. Then, the score will be calculated according to the following table:

In some test cases the behavior of the grader is adaptive. This means that 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 the prior calls to use_machine. Though, it is guaranteed that the grader answers in such a way that after each interaction there is at least one sequence of mushroom species consistent with all the answers given so far.

Sample grader

The sample grader reads an array s of integers giving the mushroom species. For all 0 ≤ i ≤ n − 1, s[i] = 0 means the species of mushroom i is A, whereas s[i] = 1 means the species of mushroom i is B. The sample grader reads input in the following format:

• line 1: n
• line 2: s[0] s[1] ... s[n - 1]

The output of sample 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 sample grader is not adaptive.

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Counting Mushrooms)

(mushrooms)

Andrew the mushroom expert is investigating mushrooms native to Singapore.

As part of his research, Andrew collected n mushrooms labelled 0 to n - 1. Each mushroom is of one of two species, which are called A and B.

Andrew knows that mushroom 0 belongs to species A, but as the two species look the same, he does not know the species of mushrooms 1 to n - 1.

Fortunately, Andrew has a machine in his lab that can help with this. To use this machine, one should place two or more mushrooms in a row inside the machine (in any order) and turn the machine on. Then, the machine calculates the number of adjacent pairs of mushrooms that are of different species. For example, if you place mushrooms of species [A, B, B, A] (in that order) into the machine, the result will be 2.

However, as operating the machine is very expensive, the machine can be used for a limited number of times. In addition, the total number of mushrooms placed in the machine across all its uses cannot exceed 100 000. Use this machine to help Andrew count the number of mushrooms of species A collected.

Implementation details

You should implement the following procedure:

int count_mushrooms(int n)

• n: number of mushrooms collected by Andrew.
• This procedure is called exactly once, and should return the number of mushrooms of species A.

The above procedure can make calls to the following procedure:

int use_machine(int[] x)

• x: an array of length between 2 and n inclusive, describing the labels of the mushrooms placed in the machine, in order.
• The elements of x must be distinct integers from 0 to n - 1 inclusive.
• Let d be the length of array x. Then, the procedure returns the number of different indices j, such that 0 ≤ j ≤ d - 2 and mushrooms x[j] and x[j + 1] are of different species.
• This procedure can be called at most 20 000 times.
• The total length of x passed to the procedure use_machine among all its invocations cannot exceed 100 000.

Examples

Example 1

Consider a scenario in which there are 3 mushrooms of species [A, B, B], in order. The procedure count_mushrooms is called in the following way:

count_mushrooms(3)

This procedure may call use_machine([0, 1, 2]), which (in this scenario) returns 1. It may then call use_machine([2, 1]), which returns 0.

At this point, there is sufficient information to conclude that there is only 1 mushroom of species A. So, the procedure count_mushrooms should return 1.

Example 2

Consider a case in which there are 4 mushrooms with species [A, B, A, A], in order. The procedure count_mushrooms is called as below:

count_mushrooms(4)

This procedure may call use_machine([0, 2, 1, 3]), which returns 2. It may then call use_machine([1, 2]), which returns 1.

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

Constraints

Do note that you DO NOT necessarily have to solve for the general case, but only for the subproblem defined by the following constraints:
You only need to solve for very simple cases, such as those in the examples shown.

Scoring

If in any of the test cases, the calls to the procedure use_machine do not conform to the rules mentioned above, or the return value of count_mushrooms is incorrect, the score of your solution will be 0. Otherwise, let Q be the maximum number of calls to the procedure use_machine among all test cases. Then, the score will be calculated according to the following table:

In some test cases the behavior of the grader is adaptive. This means that 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 the prior calls to use_machine. Though, it is guaranteed that the grader answers in such a way that after each interaction there is at least one sequence of mushroom species consistent with all the answers given so far.

Sample grader

The sample grader reads an array s of integers giving the mushroom species. For all 0 ≤ i ≤ n − 1, s[i] = 0 means the species of mushroom i is A, whereas s[i] = 1 means the species of mushroom i is B. The sample grader reads input in the following format:

• line 1: n
• line 2: s[0] s[1] ... s[n - 1]

The output of sample 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 sample grader is not adaptive.

Execution limits

Your solution will have 2.0 second(s) execution time and 1024 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "mushrooms.h"

int count_mushrooms(int n) {
    std::vector<int> m;
    for (int i = 0; i < n; i++)
        m.push_back(i);
    int c1 = use_machine(m);
    m = {0, 1};
    int c2 = use_machine(m);
    return c1+c2;
}

参考代码

#include "mushrooms.h"

int count_mushrooms(int n) {
    std::vector<int> m;
    for (int i = 0; i < n; i++)
        m.push_back(i);
    int c1 = use_machine(m);
    m = {0, 1};
    int c2 = use_machine(m);
    return c1+c2;
}

请将你的实现写入 submission.cpp（可沿用上面的框架与题目头文件）。判题时你的代码会与题目自带的 manager / grader 一起编译链接，并按题目规定的协议通信。

本题为交互题：你的程序需与题目自带的 manager 进程通信（按题目约定经标准输入输出或命名管道），无需自行读取测试数据。

由 manager 进程打印判定结果，无需自行写出答案。

include "mushrooms.h"

int count_mushrooms(int n) {
std::vector<int> m;
for (int i = 0; i < n; i++)
m.push_back(i);
int c1 = use_machine(m);
m = {0, 1};
int c2 = use_machine(m);
return c1+c2;
}