| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 42 | 22 | 20 | 52.632% |
Do you know Just Odd Investigations Laboratory? The business of this laboratory is to do “just odd investigations.” In the following, we call it JOI Laboratory for short.
In recent years, broad gardens with splendid flowers were discovered in several historical ruins in the world. JOI Laboratory discovered that the flowers in these gardens are new species, and their genes have similar features. The genes of these new flowers are strings of length N consisting of J, O, I. These strings are called gene sequences.
You are a researcher working in JOI Laboratory. You initially have three flowers of new species. Their gene sequences are SA, SB, SC, respectively.
You can obtain a flower of new species from two flowers of new species by an operation called crossing. The i-th character (1 ≤ i ≤ N) of the gene sequence of the new flower is determined by the following rule.
J, O, or I which is different from these two characters.In other words, if the i-th characters of the gene sequences of the two flowers are c1 and c2, the i-th character c3 of the gene sequence of the new flower is given by the following table.
| c1 | J | J | J | O | O | O | I | I | I |
|---|---|---|---|---|---|---|---|---|---|
| c2 | J | O | I | J | O | I | J | O | I |
| c3 | J | I | O | I | O | J | O | J | I |
You may use the same flower for crossing as many times as you want. If you obtain a new flower by crossing, you may use it for subsequent crossings.
In order to obtain more beautiful flowers, JOI Laboratory proposed (Q + 1) gene sequences numbered from 0 to Q as candidate gene sequences. You are given a list describing the candidate gene sequences. The list contains a string T0 and, for each j (1 ≤ j ≤ Q), integers Lj, Rj and a character Cj. The candidate gene sequences are given as follows.
Write a program which, given an integer N, the gene sequences of the three initial flowers, and the list describing the candidate gene sequences, determines, for each candidate gene sequence, whether it is possible to obtain a flower whose gene sequence is the given one from the three initial flowers by crossing zero or more times.
Read the following data from the standard input.
N SA SB SC Q T0 L1 R1 C1 . . . LQ RQ CQ
Write (Q + 1) lines to the standard output. In the (j + 1)-th line (0 ≤ j ≤ Q), output Yes if it is possible to obtain a flower whose gene sequence is the candidate gene sequence j from the three initial flowers by crossing zero or more times. Otherwise, output No.
J, O, or I.J, O, or I.J, O, or I (1 ≤ j ≤ Q).| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | SA = SB = SC, N ≤ 100. |
| 2 | 23 | SA = SB = SC. |
| 3 | 23 | N ≤ 100. |
| 4 | 51 | No additional constraints. |
4 JOJO JJOI OJOO 3 IJOJ 1 4 O 2 2 J 2 4 I
Yes No Yes Yes
The gene sequences of the three initial flowers are JOJO, JJOI, and OJOO. In the following, new flowers obtained by crossing are written as their gene sequences.
IJOJ. Since it is possible to obtain IJOJ by crossing JJOI with OJOO, output Yes.OOOO. Since it is impossible to obtain OOOO from the three initial flowers by crossing zero or more times, output No.OJOO. Since you have OJOO in the beginning without crossing, output Yes.OIII. You can obtain IJOJ by crossing JJOI with OJOO. Then you can obtain OIII by crossing JOJO with IJOJ. Therefore, output Yes.This sample input satisfies the constraints of Subtasks 3, 4.
3 JOI JOI JOI 2 OJI 1 2 O 1 1 J
No No Yes
The gene sequences of the three initial flowers are JOI only. You can obtain JOI only by crossing.
OJI. Since it is impossible to obtain this flower by crossing, output No.OOI. Since it is impossible to obtain this flower by crossing, output No.JOI. Since it is possible obtain this flower, output Yes.This sample input satisfies the constraints of Subtasks 1, 2, 3, 4.