시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
JOICup is a popular television variety program held by JOI broadcast station. Now JOICup becomes the final round. In the final round, the “messenger game” will be played. Only one team which passed the first round will play the game. The team consists of two players, Anna and Bruno,
In the messenger game, the players send information using a grid of $8 \times 8$ cells. The rows of the grid are numbered from $0$ to $7$, and the columns of the grid are numbered from $0$ to $7$.
In the messenger game, Anna and Bruno are isolated in different rooms. They will play $Q$ challenges. The $i$-th challenge ($1 ≤ i ≤ Q$) proceeds as follows.
A
’ and ‘B
’ are written. All of the cells in the grid are white.The challenges proceed as in the following figure.
Write programs which implement the strategies of Anna and Bruno to win the “messenger game.” For the grading of this task, see Grading.
You need to submit two files.
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
.
void Anna(int X, int Y, int N, std::string S)
This function is called $Q$ times. The $i$-th call ($1 ≤ i ≤ Q$) corresponds to the procedures 1., 2., 3. of the $i$-th challenge of the game.
X
is the integer $X_i$ written on the card given to Anna in the procedure 1. of the $i$-th challenge.Y
is the integer $Y_i$ written on the card given to Anna in the procedure 1. of the $i$-th challenge.N
is the integer $N_i$ written on the card given to Anna in the procedure 1. of the $i$-th challenge.S
is the string $S_i$ written on the card given to Anna in the procedure 1. of the $i$-th challenge.For each function call to Anna
, the following function should be called $49$ times in total. The following function should be called once for each of the $49$ cells whose row is different from $X_i$ and column is different from $Y_i$.
void Paint(int a, int b, int c)
a
, b
mean Anna paints the cell whose row is a
and column is b
. Here the conditions $0 ≤ a ≤ 7$, $0 ≤ b ≤ 7$, a ≠ X
, b ≠ Y
should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [1].c
means the color painted by Anna is blue if c = 0
, and red if c = 1
. Here, $0 ≤ c ≤ 1$ should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [2].Paint
is called with the same parameters (a, b)
more than once, your program is judged as Wrong Answer [3].Anna
terminates, if the number of function calls to Paint
is different from $49$, your program is judged as Wrong Answer [4].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
.
std::string Bruno(int N, std::vector<std::vector<int>> T)
This function is called every time when Anna finishes painting the grid. This function is called $Q$ times in total. The $i$-th call ($1 ≤ i ≤ Q$) corresponds to the procedures 5., 6. of the $i$-th challenge of the game.
N
is the integer $N_i$ written on the card given to Bruno in the procedure 5. of the $i$-th challenge.T
is a two-dimensional array of size $8 \times 8$ corresponding to the grid of cells given to Bruno in the procedure 5. of the i-th challenge. The color of the cell whose row is a
($0 ≤$ a
$≤ 7$) and column is b
($0 ≤$ b
$≤ 7$) is blue if T[a][b] = 0
, and red if T[a][b] = 1
.A
’ or ‘B
’. If this condition is not satisfied, your program is judged as Wrong Answer [6].Your program can implement other functions for internal use, or use global variables. Submitted files will be compiled with the grader, and become a single executable file. All global variables and internal functions should be declared in an unnamed namespace to avoid confliction with other files. When it is graded, it will be executed as two processes of Anna and Bruno. The process of Anna and the process of Bruno cannot share global variables.
Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.
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. Instead, you may run compile.sh
contained in the archive file.
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. In particular, Bitaro does not necessarily choose the colors to paint the cells randomly. 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.
$Q$
$X_1$ $Y_1$ $N_1$ $S_1$
$X_2$ $Y_2$ $N_2$ $S_2$
$\vdots$
$X_Q$ $Y_Q$ $N_Q$ $S_Q$
Output of the Sample Grader
The sample grader outputs the following information to the standard output (quotes for clarity).
Accepted: 28
”. For the value of $L^*$, see Grading.If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.
In sample grader, the colors chosen by Bitaro for challenges are randomly determined by pseudorandom numbers whose results do not change for different executions. In order to change the seed of pseudorandom numbers, run the sample grader with the first integer argument as follows.
./grader 2023
A
’ and ‘B
’.If your program is judged as any type of Wrong Answer [1]–[6] (see Implementation Details) or any type of runtime errors (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), Abnormal End, etc.) in any of the test cases, your score is 0 point regardless of whether your program wins challenges in other test cases.
Otherwise, let $L^*$ be the minimum of the following values for all test cases of this task. Your score is calculated as in the following table.
$L^*$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score | $0$ | $5$ | $8$ | $10$ | $11$ | $13$ | $14$ | $16$ | $18$ | $19$ | $21$ | $22$ | $24$ | $26$ | $27$ |
$L^*$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ | $21$ | $22$ | $23$ | $24$ | $25$ | $26$ | $27$ | $28$ | $29$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score | $29$ | $30$ | $32$ | $34$ | $35$ | $37$ | $38$ | $40$ | $42$ | $43$ | $45$ | $46$ | $48$ | $50$ | $51$ |
$L^*$ | $30$ | $31$ | $32$ | $33$ | $34$ | $35$ | $36$ | $37$ | $38$ | $39$ | $40$ | $41$ | $42$ | $43$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score | $53$ | $54$ | $56$ | $57$ | $59$ | $60$ | $62$ | $65$ | $68$ | $71$ | $74$ | $77$ | $84$ | $100$ |
Here is a sample input for the sample grader and corresponding function calls. The parameters $T$ for the function calls to Bruno
are omitted.
Sample Input 1 | Sample Function Calls | ||
---|---|---|---|
Function call to Anna | Function call to Bruno | Return value of Bruno | |
2 0 0 1 B 5 7 8 AAAABBBB |
Anna(0, 0, 1, "B") |
||
Paint(1, 1, 0) |
|||
Paint(1, 2, 1) |
|||
... |
|||
Paint(7, 7, 1) |
|||
Bruno(1, ...) |
|||
"B" |
|||
Anna(5, 7, 8, "AAAABBBB") |
|||
Paint(0, 0, 1) |
|||
Paint(0, 1, 1) |
|||
... |
|||
Paint(7, 6, 0) |
|||
Bruno(8, ...) |
|||
"AAAABBBB" |
In this sample input, there are $Q$ ($= 2$) challenges.
In the first challenge, we have $X_1 = 0$, $Y_1 = 0$, $N_1 = 1$, $S_1 =$ “B”
. Anna paints the $49$ cells whose row is different from $0$ and column is different from $0$.
In the second challenge, we have $X_2 = 5$, $Y_2 = 7$, $N_2 = 8$, $S_2 =$ “AAAABBBB”
. Anna paints the $49$ cells whose row is different from $5$ and column is different from $7$.
For example, if your program calls Paint(0, 2, 1)
in the first challenge, it is judged as Wrong Answer [1] because it designates a cell whose row is $0$.
Here is another sample input for the sample grader.
30 3 1 1 A 1 4 1 A 6 6 2 AA 1 1 2 BB 3 1 3 BAB 7 4 3 AAB 6 4 4 BAAB 6 7 4 BABA 3 3 5 BABBA 1 5 5 ABBBA 4 3 6 ABBBBB 2 1 6 ABAAAA 6 0 7 AAABABA 6 6 7 BBABBAA 0 4 8 AABAABAB 2 1 8 AABBBBBA 2 0 9 BABABBAAA 1 5 9 BBAAABABB 6 7 10 BAAABAAABB 1 7 10 BBBBBBBABA 2 6 12 AABAABABABAB 3 4 15 BBAABAAAABABAAB 5 6 18 BAAAABBABABBBABBAB 7 0 22 BABBAABAAABBABBBBBBABA 2 0 26 AAAABBABBAAAAABABABBAABAAA 0 7 30 AAABBBAAABAABBBBAABBAAABBBABBB 2 7 34 BABAABBAABABBABAABBABBABAABBBBABBB 2 5 38 BBBBAABAABAABABABBBBBAAABBABAAABAAABBB 5 2 41 AABABBAAABBABAAAABBABABBAAAAAABBABBABBABA 1 0 43 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAAB