The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

The Last Battle
JOICup is a popular television variety program held by JOI broadcast station. Now JOICup becomes the finalround. In the final round, the “messenger game” will be played. Only one team which passed the first roundwill 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 × 8 cells. The rows of the grid arenumbered 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 diﬀerent rooms. They will play Q challenges. Thei-th challenge (1 ≤ i ≤ Q) proceeds as follows.
1. Bitaro, the moderator of the game, gives a card and a grid of 8 × 8 cells to Anna. On the card, threeintegers Xi , Yi , Ni (0 ≤ Xi ≤ 7, 0 ≤ Yi ≤ 7, 1 ≤ Ni ≤ 43) and a string S i of length Ni consisting of ‘A’and ‘B’ are written. All of the cells in the grid are white.
2. Anna paints each of the 49 cells whose row is diﬀerent from Xi and column is diﬀerent from Yi . Thecolor of each cell is either blue or red.
3. Anna gives the grid of cells to Bitaro, the moderator of the game.
4. Bitaro paints each of the 15 cells whose row is equal to Xi or column is equal to Yi . The color of eachcell is either blue or red. This process is done in a room which is not seen by Anna nor Bruno.
5. Bitaro, the moderator of the game, gives a card and the grid of cells to Bruno. Only the integer Ni iswritten on the card.
6. Bruno writes a string on a paper. If it coincides with S i , Anna and Bruno win the game.
The challenges proceed as in the following figure.
① Give the cardAnna

and the grid of cells② Paint 49 cells③ Give the gridof cells

BitaroBruno④ Paint 15 cells⑥ Write a stringon the paper⑤ Give the cardand the grid of cells

Write programs which implement the strategies of Anna and Bruno to win the “messenger game.” For thegrading of this task, see Grading.

The Last Battle– 1 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last BattleImplementation Details
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 thei-th challenge of the game.
◦ The parameter X is the integer Xi written on the card given to Anna in the procedure 1. of the i-thchallenge.
◦ The parameter Y is the integer Yi written on the card given to Anna in the procedure 1. of the i-thchallenge.
◦ The parameter N is the integer Ni written on the card given to Anna in the procedure 1. of the i-thchallenge.
◦ The parameter S is the string S i written on the card given to Anna in the procedure 1. of the i-thchallenge.
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 diﬀerent from Xi and column isdiﬀerent from Yi .

⋆ void Paint(int a, int b, int c)⋄ The parameters a, b mean Anna paints the cell whose row is a and column is b. Here theconditions 0 ≤ a ≤ 7, 0 ≤ b ≤ 7, a , X, b , Y should be satisfied. If this condition is notsatisfied, your program is judged as Wrong Answer [1].
⋄ The parameter 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 asWrong Answer [2].
⋄ If the function Paint is called with the same parameters (a, b) more than once, your programis judged as Wrong Answer [3].
⋄ When the function Anna terminates, if the number of function calls to Paint is diﬀerent from49, your program is judged as Wrong Answer [4].

The Last Battle– 2 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

The second file is Bruno.cpp. It should implement Bruno’s strategy. It should implement the followingfunction. 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.
◦ The parameter N is the integer Ni written on the card given to Bruno in the procedure 5. of the i-thchallenge.
◦ The parameter T is a two-dimensional array of size 8 × 8 corresponding to the grid of cells given toBruno in the procedure 5. of the i-th challenge. The color of the cell whose row is a (0 ≤ a ≤ 7) andcolumn is b (0 ≤ b ≤ 7) is blue if T[a][b] = 0, and red if T[a][b] = 1.
◦ The return value is the string written by Bruno on a paper.
◦ If the return value is a string of length 44 or more, your program is judged as Wrong Answer [5].
◦ Each character of the return value should be either ‘A’ or ‘B’. If this condition is not satisfied, yourprogram is judged as Wrong Answer [6].

Important Notices• 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 internalfunctions should be declared in an unnamed namespace to avoid confliction with other files. When it isgraded, it will be executed as two processes of Anna and Bruno. The process of Anna and the process ofBruno 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 tothe standard error.

The Last Battle– 3 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

Compilation and Test Run
You can download an archive file from the contest webpage which contains the sample grader to test yourprogram. 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 diﬀerent from the sample grader. In particular, Bitaro does not necessarilychoose 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
X1 Y1 N1 S 1
X2 Y2 N2 S 2..
.
XQ YQ NQ S Q

Output of the Sample Grader
The sample grader outputs the following information to the standard output (quotes for clarity).
• If your program is judged as correct, it writes the value of L∗ as “Accepted: 28”. For the value of L∗ ,see Grading.
• If your program is judged as any type of Wrong Answer, the sample grader writes its type as“Wrong Answer [1]”.
If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only
one of them.

The Last Battle– 4 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

In sample grader, the colors chosen by Bitaro for challenges are randomly determined by pseudorandom
numbers whose results do not change for diﬀerent executions. In order to change the seed of pseudorandom
numbers, run the sample grader with the first integer argument as follows.
./grader 2023

Constraints• 1 ≤ Q ≤ 20 000.
• 0 ≤ Xi ≤ 7 (1 ≤ i ≤ Q).
• 0 ≤ Yi ≤ 7 (1 ≤ i ≤ Q).
• 1 ≤ Ni ≤ 43 (1 ≤ i ≤ Q).
• Q, Xi , Yi , Ni are integers.
• S i (1 ≤ i ≤ Q) is a string of length Ni consisting of ‘A’ and ‘B’.

Grading
If your program is judged as any type of Wrong Answer [1]–[6] (see Implementation Details) or any type ofruntime 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.
• The maximum value of L such that Anna and Bruno win all the challenges satisfying Ni ≤ L. However,if they win all the challenges in the test cases, we set L = 43.
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

The Last Battle– 5 / 7The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

Sample Communication
Here is a sample input for the sample grader and corresponding function calls. The parameters T for thefunction calls to Bruno are omitted.
Sample Input 1

Sample Function Calls
Function callto Bruno

Function call to Anna
2

Anna(0, 0, 1, "B")0 0 1 B

Paint(1, 1, 0)

5 7 8 AAAABBBBPaint(1, 2, 1)...

Return valueof Bruno

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 X1 = 0, Y1 = 0, N1 = 1, S 1 = “B”. Anna paints the 49 cells whose row
is diﬀerent from 0 and column is diﬀerent from 0.
• In the second challenge, we have X2 = 5, Y2 = 7, N2 = 8, S 2 = “AAAABBBB”. Anna paints the 49 cells
whose row is diﬀerent from 5 and column is diﬀerent 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.

The Last Battle– 6 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

Here is another sample input for the sample grader.
Sample Input 230
3 1 1 A1 4 1 A6 6 2 AA1 1 2 BB3 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 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAABThe Last Battle– 7 / 7