영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Let us define a labyrinth as follows:
- The labyrinth consists of K rooms, where some pairs of rooms are connected by corridors.
- It is possible to get between every pair of rooms by walking through a sequence of corridors.
- No room has a corridor to itself.
- There may be several corridors connecting the same pair of rooms.
- Every corridor has one of three colors: red, green or blue.
- Every room has exactly three corridors, one of each color.
- One room is the entrance of the labyrinth, and one room is the exit of the labyrinth (these are different rooms).
The sisters Rosa and Lila are playing a game where Rosa first constructs a labyrinth, after which Lila tries to complete it by walking from the entrance to the exit. They have played a few times now, and Lila always manages to win. This makes Rosa rather frustrated. She wants her sister to be stuck in the labyrinth forever.
Rosa has noticed, however, that Lila always uses the same predictable strategy. More precisely, she has a string S consisting of the letters R, G and B (red, green and blue), whose length we write as |S|. On move number t, Lila looks at the tth character and follows the corridor of the color that the letter represents (so if the letter is R, Lila will walk through the red corridor of the room she is currently in). After |S| moves she starts over by looking at the first character again. In other words, if the string is RGB she will first walk through the red corridor of the entrance, then the green corridor of the room she arrived in, then the blue corridor, then the red one (she has now started reading the string from the beginning again), green, blue, red, and so on. Note that every room has exactly one corridor of each color, so the room she goes to at each step is uniquely determined.
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: An example labyrinth.
Given S, your task is to construct a labyrinth that Lila can never complete.
Input
The input contains the string S (3 ≤ |S| ≤ 400001), consisting of the letters R, G and B.
In this problem you can additionally download all of the input at the bottom of the page.
Output
Begin by printing three integers K, i and u (2 ≤ K ≤ 2|S|, 0 ≤ i,u < K, i ≠ u). K should be the number of rooms in the labyrinth you construct. i and u should be the zero-indexed numbers (that is, between 0 and K - 1) of the rooms that are the entrance and the exit of the labyrinth.
Then print K lines, one for each room, ordered by room number starting with room 0. The line for room j should contain three integers r, g and b (0 ≤ r,g,b < K) – the rooms that the red, green and blue corridors of room j lead to, respectively.
Your labyrinth must satisfy the conditions in the problem description.
Scoring
In total the problem has 11 test cases, one of which is the sample. You are not scored on the sample, but on the 10 remaining test cases.
Let K_min be the number of rooms in the smallest labyrinth that any contestant managed to construct for a given test case during the contest, and let K be the number of rooms in your labyrinth. Let
r_1 = K/(K_min)
and
r_2 = (2|S|)/(K_min)
where |S| is the length of the string S.
Your score on that test case is then
min(10, 10 · (1 - (log(r_1))/(log(r_2)))),
or 0 if K exceeds 2|S|.
예제
예제 1
RGB
4 0 3 1 3 2 0 2 3 3 1 0 2 0 1