21790번 - Ancient Machine 서브태스크점수다국어언어 제한함수 구현투 스텝피드백

Anna and Bruno are archaeologists. They excavate ruins of IOI Kingdom. In the ruin A, Anna discovered the layout of an old machine. In the ruin B, Bruno discovered the actual machine.

This machine consists of N devices. The devices are attached to an electric wire in a row. There are three types of devices called X, Y, Z. From the left, the devices are numbered from 0 through N − 1. The type of the device i (0 ≤ i ≤ N − 1) is S_i. In other words, S_i is either X, Y, or Z.

Since the machine is too big, Bruno decided to remove the devices, one by one, from the machine. However, since the devices interact with each other by an electric wire, he must be very careful about the order of removal.

Concerning a way to remove a device from the machine, we define the following.

• Assume that the devices x, y,z (0 ≤ x < y < z ≤ N − 1) are not yet removed, and S_x = X, S_y = Y, S_z = Z. Moreover, assume that, for every x < j < y, the device j was already removed, and, for every y < k < z, the device k was already removed. If all of these conditions are satisfied and we remove the device y from the machine, it is called a good removal.
• Any other way to remove a device from the machine is not a good removal.

Bruno has to remove all of the N devices from the machine so that the number of good removals is the maximum possible. However, since the three types of devices look similar, he cannot distinguish the types of the devices.

Since Anna has the layout of the machine, she knows the type of each device attached to the machine. Thus, she will use a transmitter to help Bruno. Using the transmitter, she can send a sequence of characters. Each character she can send is either 0 or 1.

Write a program which implements Anna’s strategy and Bruno’s strategy so that the number of good removals is the maximum possible. In this task, if the number of characters sent by Anna to Bruno is smaller, your will get higher score.

You need to submit two files.

The first file is Anna.cpp. It should implement Anna’s strategy. It should implement the following function. The program should include Anna.h using the preprocessing directive #include.

• void Anna(int N, std::vector<char> S)
  For each test case, this function is called exactly once in the beginning.
  • The parameter N is the number of devices N.
  • The parameter S is an array of length N. This means S[i] is the type S_i of the device i (0 ≤ i ≤ N − 1). Here the character S[i] is either ‘X’, ‘Y’, or ‘Z’.

Your program can call the following function.

• void Send(int a)
  Using this function, Anna sends a character, 0 or 1, to Bruno.
  • The parameter a is an information sent to Bruno. It should be 0 or 1. If this condition is not satisfied, your program is judged as Wrong Answer [1].
  • The function Send should not be called more than 200 000 times. If it is called more than 200 000 times, your program is judged as Wrong Answer [2].

The second file is Bruno.cpp. It should implement Bruno’s strategy. It should implement the following function. The program should include Bruno.h using the preprocessing directive #include.

• void Bruno(int N, int L, std::vector<int> A)
  After the function Anna is called, this function is called exactly once.
  • The parameter N is the number of devices N.
  • The parameter L is the number L of characters, 0 or 1, sent by Anna.
  • The parameter A is an array of length L. It means Anna sent the sequence A[0],A[1],...,A[L-1] of characters to Bruno, in this order. Each character of the sequence is either 0 or 1.

Your program can call the following function.

• void Remove(int d)
  Using this function, your program answers how to remove the devices.
  • The parameter d is the index of a device. It means Bruno removes the device d.
  • The inequalities 0 ≤ d ≤ N − 1 should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [3].
  • It is not allowed to call this function with same parameter d more than once. If this condition is not satisfied, your program is judged as Wrong Answer [4].
  • The function Remove should be called exactly N times. When the function Bruno terminates, if the number of calls to the function Remove is different from N, your program is judged as Wrong Answer [5].
  • After all the N devices are removed, the number of good removals should be the maximum possible. If this condition is not satisfied, your program is judged as Wrong Answer [6].

The sample grader reads the following data from the standard input.

N
S0 S1 · · · SN−1

Here S_i and S_i+1 (0 ≤ i ≤ N − 2) are separated by a space.

When the program terminates successfully, the sample grader writes the following information to the standard output (quotes for clarity).

• If your program is judged as any one of Wrong Answer [1], [2], [3], [4], or [5], it writes its type as “Wrong Answer [1]”.
• Otherwise, it writes the number L of function calls to Send and the number D of good removals as “Accepted: L D”. Note that the behavior of the sample grader is different from the actual grader. The sample grader does not check whether your program is judged as Wrong Answer [6] or not.

If your program is judged as several types of Wrong Answer [1], [2], [3], [4], or [5], the sample grader reports only one of them.

• 3 ≤ N ≤ 100 000.
• S_i is one of X, Y, or Z (0 ≤ i ≤ N − 1).

N ≤ 18.

No additional constraints. In this Subtask, your score is calculated by the following way.

• Let L be the maximum of the number of function calls to Send for every test case of this Subtask.
• Then your score is calculated as follows.
  • If 160 000 < L ≤ 200 000, your score is 25 + ⌊10 × ((200000 − L) / 40000)⌋ points.
  • If 100 000 < L ≤ 160 000, your score is 35 + ⌊30 × ((160000 − L) / 60000)⌋ points.
  • If 70 000 < L ≤ 100 000, your score is 65 + ⌊30 × ((100000 − L) / 30000)²⌋ points.
  • If L ≤ 70 000, your score is 95 points.

Here ⌊x⌋ is the largest integer not exceeding x.

Here is a sample input for the sample grader and corresponding function calls.

4
X Y X Z

In these sample function calls, the 4 devices will be removed by the following way.

1. In the beginning, the 4 devices are X Y X Z.
2. Bruno removes the device 2. The devices become X Y - Z. Here - means the device in this position was already removed.
3. Bruno removes the device 1. The devices become X - - Z. Since (x, y,z) = (0, 1, 3) satisfies the condition, it is a good removal.
4. Bruno removes the device 0. The devices become - - - Z.
5. Finally, Bruno removes the device 3. The devices become - - - -. The number of good removals is 1.

In this sample input, the number of good removals cannot be greater than 1.

• ancient_machine-dist.zip