The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Tricolor Lights

Tricolor Lights
Anna and Bruno, experts in gambling, are about to compete against Dealer D-taro in a game.
During the game, Anna and Bruno are isolated in separate rooms and can only communicate through Dealer
D-taro.
In this game, they use a row of N lights. These lights are numbered from 1 to N from left to right and can beilluminated in one of three colors: red, green, or blue.
At the beginning of the game, Anna illuminates each of these lights in either red, green, or blue. Additionally,Dealer D-taro speciﬁes one prohibited color for each light, represented by a string S of length N. Let S i denotethe i-th character of S (1 ≤ i ≤ N). If S i is ‘R’, the prohibited color for light i is red; if S i is ‘G’, it’s green; and if
S i is ‘B’, it’s blue. Anna cannot illuminate light i in its prohibited color. For example, if S 1 is ‘R’, Anna cannot
illuminate light 1 in red. Dealer D-taro conveys the information of the prohibited color for each light to Anna
but not to Bruno.
After illuminating each light, Anna selects an integer l satisfying 1 ≦ l ≦ min(N, 130) and informs DealerD-taro. Dealer D-taro then informs Bruno of the total number of lights N and the integer l chosen by Anna.
Subsequently, they proceed with Q rounds as follows:
1. Dealer D-taro selects an integer a j between 1 and N − l + 1 and shows Bruno the sequence of colors
illuminated for lights a j , a j + 1, . . . , a j + l − 1.
2. Bruno responds with a single integer to Dealer D-taro based on the sequence of colors shown. If theinteger matches a j , Anna and Bruno win the round.
However, Dealer D-taro may vary the selection of a1 , a2 , . . . , aQ based on the sequence of colors illuminatedby Anna and the chosen integer l.
You are required to implement a program that allows Anna and Bruno to win all Q rounds.

Tricolor Lights– 1 / 6

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying TrialMarch 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Tricolor Lights

Implementation Details
You need to submit 2 ﬁles.
The ﬁrst ﬁle is Anna.cpp. It should implement Anna’s strategy. It should implelment the following functions.
The program should include Anna.h using the preprocessing directive #include.
• std::pair<std::string, int> anna(int N, std::string S)
This function is called once initially.
◦ The parameter N is the number of lights.
◦ The parameter S is a string of length N representing the prohibited colors speciﬁed by Dealer D-taro.
◦ The return value is a pair consisting of a string t representing the colors Anna illuminates for eachlight and an integer l chosen by Anna. Let ti denote the i-th character of t (1 ≤ i ≤ N). ti signiﬁes
Anna illuminating the i-th lamp with color ti If ti is ‘R’, the prohibited color for light i is red; if ti is‘G’, it’s green; and if ti is ‘B’, it’s blue.
◦ The length of string t must be N. Otherwise, it will be judged as Wrong Answer [1].
◦ Each character in string t must be ‘R’, ‘G’, or ‘B’. Otherwise, it will be judged as Wrong Answer[2].
◦ Each character of string t must be diﬀerent from the corresponding character in S . Otherwise, it will
be judged as Wrong Answer [3].
◦ l must be between 1 and min(N, 130). Otherwise, it will be judged as Wrong Answer [4].
The second ﬁle is Bruno.cpp. It should implement Bruno’s strategy. It should implelment the following
functions. The program should include Bruno.h using the preprocessing directive #include.
• void init(int N, int l) This function is called once initially.
◦ The parameter N is the number of lights.
◦ The parameter l is the integer chosen by Anna.
• int bruno(std::string u) This function is called Q times after function init is called and corresponds to steps 1 and 2 of each round in the game.
◦ The argument u is a string of length l consisting of ‘R’, ‘G’, ‘B’, representing the sequence of colors
illuminated for lights a j , a j + 1, . . . , a j + l − 1.
◦ Let uk denote the k-th character of u (1 ≤ k ≤ N). If uk is ‘R’, the color of a j + k − 1-th light that
Anna illuminated is red; if uk is ‘G’, it’s green; and if uk is ‘B’, it’s blue.
◦ The return value is the integer Bruno responds with.
◦ The return value must match a j . Otherwise, it will be judged as Wrong Answer [5].

Tricolor Lights– 2 / 6

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Tricolor Lights

Important Notices• Your program can implement other functions for internal use, or use global variables. Submitted ﬁles
will be compiled with the grader, and become a single executable ﬁle. All global variables and internalfunctions should be declared in an unnamed namespace to avoid conﬂiction with other ﬁles. 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 ﬁles by any methods. However, your program may output debugging information tothe standard error.

Compilation and Test Run
You can download an archive ﬁle from the contest webpage which contains the sample grader to test yourprogram. The archive ﬁle also contains a sample source ﬁle of your program.
The sample grader is the ﬁle 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 ﬁle.
g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
When the compilation succeeds, the executable ﬁle grader is generated.
Note that the actual grader is diﬀerent 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 and thestandard error output.

Tricolor Lights– 3 / 6

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Tricolor Lights

Input of the Sample Grader
The sample grader reads the following data from the standard input.
NSQ
a1 a2 · · · aQ
Unlike the actual grading program, the sample grading program must have ﬁxed answers. a j (1 ≦ j ≦ Q)
represents the integer a j chosen by Dealer D-taro in the jth round. In your program, a j must satisfy 1 ≤ a j ≤N − l + 1 for the integer l chosen by Anna.

Output of the Sample Grader
The sample grader outputs the following information to the standard output and the standard error output(quotes for clarity).
• For correct answers, “Accepted: 130” is output for the integer l chosen by Anna.
• For wrong answers, the type of wrongness is output, such as “Wrong Answer [1]”.
If your program meets the conditions of several types of Wrong Answer, the sample grader reports only oneof them.

Grading Considerations
The actual grading program determines a1 , a2 , . . . , aQ based on the sequence of colors illuminated by Anna
and the chosen integer l. But Bruno’s response does not aﬀect the selection of a1 , a2 , . . . , aQ .

Constraints• 1 ≤ N ≤ 500 000．
• 1 ≤ Q ≤ 10 000．
• S is a string of length N consisting of ‘R’,‘G’, or ‘B’.
• N and Q are integers.

Tricolor Lights– 4 / 6

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Tricolor Lights

Subtasks
1. (5 points) N ≤ 131．
2. (5 points) N ≤ 250．
3. (5 points) N ≤ 380．
4. (15 points) N ≤ 7 000．
5. (70 points) No additional constraints. In this subtask, points are awarded as follows:• Let l∗ denote the maximum value of l chosen by Anna in all test cases of this subtask.
• If any test case in this subtask is judged as Wrong Answer [1] 〜 [5] (see implementation details)
or exceeds the time limit, memory limit, or encounters a runtime error, the subtask score is 0 points.
• If all test cases in this subtask are correct, the subtask score is determined as follows:
the value of l∗score

61 < l∗ ≦ 130

10 points∗

41 < l ≦ 61

20 points

34 < l∗ ≦ 41

25 + 3 × (41 − l∗ ) points

28 < l∗ ≦ 34

46 + 4 × (34 − l∗ ) pointsl∗ ≦ 2870 points

Tricolor Lights– 5 / 6The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Tricolor Lights

Sample Communication
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1

Sample Function Calls
Call

Return value

8anna(8, "RGGBRBBG")("BBRGBGRR", 5)

RGGBRBBG

init(8, 5)

2bruno("RGBGR")

3

3 1

bruno("BBRGB")

1In this example, Anna receives the number of lights N = 8 and the string representing prohibited colors
S = "RGGBRBBG". Anna chooses to illuminate each light with the string t representing colors "BBRGBGRR" andselects the integer l as 5, which she communicates to Dealer D-taro. Then, Dealer D-taro informs Bruno of thenumbers N = 8 and l = 5.
In the ﬁrst round, Dealer D-taro chooses a1 = 3. Bruno receives the sequence of colors illuminated for lights
3, 4, 5, 6, and 7, represented by the string u = "RGBGR", and responds with the integer 3, which matches a1 .
Input example 1 satisﬁes all constraints for all subtasks. The ﬁle sample-01-in.txt downloadable fromthe contest site corresponds to input example 1.

Tricolor Lights– 6 / 6