시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 147 | 10 | 9 | 7.377% |
Anna and Bruno are gamble masters. They will play a game with D-taro who is the dealer of the game.
In this game, Anna and Bruno stay in different rooms. They can communicate with each other using a broken device only. D-taro gives an integer to Anna. For Anna and Bruno, the purpose of this game is to send the given integer from Anna to Bruno using the device.
When the game starts, in the beginning, Anna declares an integer $m$ between $1$ and $2\,000$, inclusive. Then they play $Q$ rounds. The round $i$ ($1 ≤ i ≤ Q$) is performed as follows.
Write programs which implements the strategies of Anna and Bruno so that theory win for all the Q rounds.
We say an array $Z$ is obtained from the arrays $X$ and $Y$ by riffle shuffle if we can divide the elements of the array $Z$ into two groups so that the following two conditions are satisfied.
For example, the array $Z = [1, 1, 1, 0, 0, 0]$ is obtained from $X = [1, 1, 0]$ and $Y = [1, 0, 0]$ by riffle shuffle because the array consisting of the first, second, fourth elements of $Z$ in the same order is the array $[1, 1, 0]$, and the array consisting of the third, fifth, sixth elements of $Z$ in the same order is the array $[1, 0, 0]$.
On the other hand, if $X = [1, 1, 0]$, $Y = [1, 0, 0]$, and $Z = [0, 0, 0, 1, 1, 1]$, the array $Z$ is not obtained from $X$ and $Y$ by riffle shuffle.
The first file is Anna.cpp
. It should implement Anna’s strategy. It should implement the following functions. The program should include Anna.h
using the preprocessing directive #include
.
int Declare()
std::pair<std::vector<int>, std::vector<int> > Anna(long long A)
Declare
is called, this function is called $Q$ times. The $i$-th call ($1 ≤ i ≤ Q$) to this function corresponds to Step 1 and Step 2 for the round $i$.
A
is the integer $A_i$ given by D-taro to Anna.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
.
long long Bruno(std::vector<int> u)
u
is the array $u_i$ sent by the device to Bruno for the round $i$.You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.
The sample grader is the file grader.cpp
. In order to test your program, put grader.cpp
, Anna.cpp
, Bruno.cpp
, Anna.h
, Bruno.h
in the same directory, and run the following command to compile your programs.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
When the compilation succeeds, the executable file grader
is generated.
Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.
Input for the Sample Grader
The sample grader reads the following data from the standard input.
$\begin{align*} & Q \\ & A_1 \\ & A_2 \\ & \vdots \\ & A_Q \end{align*}$
Output of the Sample Grader
The sample grader outputs the following information to the standard output (quotes for clarity).
Declare
as “Accepted: 2000
”.Wrong Answer [1]
”.If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.
When the sample grader is executed, the riffle shuffle for each round is calculated using pseudo random numbers. Their results do not change for executions. In order to change the seed of pseudo random numbers, execute the sample grader by the following way.
./grader 2022
The first argument should be an integer.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $A_i ≤ 2\,000$ ($1 ≤ i ≤ Q$). |
2 | 5 | $A_i ≤ 4\,000\,000$ ($1 ≤ i ≤ Q$). |
3 | 3 | $A_i ≤ 10\,000\,000$ ($= 10^7$) ($1 ≤ i ≤ Q$). |
4 | 12 | $A_i ≤ 100\,000\,000$ ($= 10^8$) ($1 ≤ i ≤ Q$). |
5 | 15 | $A_i ≤ 100\,000\,000\,000$ ($= 10^{11}$) ($1 ≤ i ≤ Q$). |
6 | 60 | No additional constraints. For this subtask, your score is calculated as follows. |
The value of $m^∗$ | Score |
---|---|
$201 ≤ m^∗ ≤ 2\,000$ | $40 - 25 × \log_{10}{\left(\frac{m^∗}{200} \right)}$ points |
$161 ≤ m^∗ ≤ 200$ | $40$ points |
$156 ≤ m^∗ ≤ 160$ | $44$ points |
$151 ≤ m^∗ ≤ 155$ | $48$ points |
$146 ≤ m^∗ ≤ 150$ | $52$ points |
$141 ≤ m^∗ ≤ 145$ | $56$ points |
$m^∗ ≤ 140$ | $60$ points |
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1 | Sample Function Calls | |
---|---|---|
Call | Return Value | |
2 42 2000 |
Declare() |
4 |
Anna(42) |
([0, 0, 1, 0], [1, 1, 0, 1]) |
|
Bruno([1, 0, 0, 1, 0, 1, 0, 1]) |
42 |
|
Anna(2000) |
([0, 1], [0, 0]) |
|
Bruno([0, 0, 1, 0]) |
2000 |
In this sample input, there are $Q$ ($= 2$) rounds. For the round $1$, D-taro gives the integer $A_1$ ($= 42$) to Anna. For the round $2$, D-taro gives the integer $A_2$ ($= 2000$) to Anna.
This sample input satisfies the constraints of all the subtasks.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)