Deque Game

시간 제한1초메모리 제한1024 MB

요약

K가지 블록으로 이루어진 알파벳에서 시작 스택 두 개가 주어질 때, 각 시작 스택을 연속된 부분으로 포함하는 서로 다른 L층 스택의 개수를 세어 두 값을 비교하는 문제다. 이때 두 시작 스택의 개수를 비교해 Y, S, YS 중 하나를 출력한다. 수가 매우 크므로 직접 세는 대신 조합적 성질을 이용해야 한다. 이 문제는 대회용으로 출제된 난도 높은 조합 문제에 가깝다. 스택을 만드는 서로 다른 방법의 수를 효율적으로 계산하는 것이 핵심이다. 각 시작 스택이 L층 스택 안에 들어갈 수 있는 위치마다 경우의 수를 더해야 하며, 겹치는 경우를 중복 없이 처리해야 한다. 이를 위해 포함배제 원리와 동적 계획법, 문자열 비교를 조합해야 한다. 결과적으로 두 수의 대소만 판정하면 되지만, 계산 과정은 결코 단순하지 않다. K가 최대 10, L이 최대 2000, 게임 수가 3000까지 주어지므로 단순 완전 탐색으로는 시간 안에 해결할 수 없다. 각 시작 스택에 대해 포함 관계를 빠르게 판정하고, 조합 수를 미리 계산해 두는 전처리가 필요하다. 따라서 이 문제는 인터뷰용이 아니라 대회용 고난도 문제로 분류한다. 두 시작 스택이 서로 다른 경우와 같은 경우를 나누어 생각해야만

난이도: 어려움10점 중 9점
유형: 동적 계획법, 조합론, 수학, 문자열
정답자: 아직 제출이 없습니다

문제

21세기 최고의 게임! 연돌이와 세순이들의 극찬을 받아낸 게임! 세계를 매혹한 게임! 바로 Deque Game입니다.

Deque Game은 두 사람이 각자 주어진 블록을 이용해 $L$ 층을 더 다양한 방식으로 쌓을 수 있는 사람이 승리하는 게임이다. Deque Game의 자세한 규칙은 다음과 같다.

총 $K$ 종류의 블록이 있고, 연돌이와 세순이는 원하는 만큼 블록을 가져다 사용할 수 있다. 블록에는 $0$ 이상 $K$ 미만의 정수가 적혀있으며, 블록을 여러 개 쌓아서 스택을 만들 수 있다.
게임 시작 전, 연돌이와 세순이는 각자 $N$ , $M$ 층의 스택을 무수히 많이 받는다. 연돌이가 받는 모든 스택은 동일하다. 세순이가 받는 모든 스택도 동일하다.
연돌이와 세순이는 매초 본인이 받은 스택 중 하나를 고른다. 그리고 임의의 블록을 끼워 넣는다. 스택의 가장 아래나, 가장 위, 심지어 중간에도 끼워 넣을 수 있다. 이미 $L$ 층이 쌓인 스택은 고르지 않는다.
충분히 많은 시간이 흐르면, 더 이상 새로운 방법으로 $L$ 층의 스택을 만들 수 없을 것이다. 이때, 둘 중 더 많은 방식으로 $L$ 층의 스택을 완성한 사람이 승리한다. 만약 $L$ 층의 스택을 완성하는 방식의 수가 같다면 승부가 나지 않는다.

예를 들어 연돌이는 $2$ 층짜리 $00$ 스택을 무수히 많이 받고, 세순이는 $2$ 층짜리 $22$ 스택을 무수히 많이 받았다. 총 $3$ 종류의 블록을 이용해서 $3$ 층 스택을 쌓는 방법의 수는 $7$ 가지로 같다. 이 Deque Game은 승부가 나지 않는다.

곧 밤 10시가 되기 때문에 마호가니 아르바이트생 선렬이는 문을 닫을 준비를 해야 한다. 하지만 이 순간에도 연돌이들과 세순이들이 Deque Game을 열심히 하고 있다. 선렬이는 매 게임판을 돌아다니며 Deque Game의 승자를 알려주기로 했다. 재빨리 Deque Game의 승자를 알려주고 게임판을 접지 않으면, 10시에 문을 닫지 못하고 벌금을 내야 할 것이다!

입력

첫 번째 줄에 마호가니에서 연돌이와 세순이가 진행하는 Deque Game의 수 $G$ 가 주어진다. ( $1 \leq G \leq 3\,000$ )

두 번째 줄에 블록 종류의 개수를 나타내는 $K$ 와 쌓아야 하는 스택의 층수를 나타내는 $L$ 이 주어진다. ( $1 \leq K \leq 10$ , $1 \leq L \leq 2\,000$ )

세 번째 줄부터 $G$ 개의 Deque Game에 대한 정보가 다음과 주어진다.

연돌이가 받은 스택의 크기를 나타내는 정수 $N$ 이 주어진다. ( $1 \leq N \leq L$ )
연돌이가 받은 스택을 나타내는 문자열 $S$ 가 주어진다. 문자열 $S$ 의 길이는 $N$ 이고, 스택을 나타내는 문자열은 최하단 블록부터 주어진다.
세순이가 받은 스택의 크기를 나타내는 정수 $M$ 이 주어진다. ( $1 \leq M \leq L$ )
세순이가 받은 스택을 나타내는 문자열 $T$ 가 주어진다. 문자열 $T$ 의 길이는 $M$ 이고, 스택을 나타내는 문자열은 최하단 블록부터 주어진다.

연돌이와 세순이가 받은 스택의 블록에는 $0$ 이상 $K$ 미만의 정수가 적혀있다.

출력

$G$ 개의 줄에 Deque Game의 승자를 출력한다.

연돌이가 승리하면 Y를, 세순이가 승리하면 S를 출력한다. 만약 승부가 나지 않는다면 YS를 출력한다.

예제2

예제 1
입력
```
1
3 3
2
00
2
22
```
예상 출력
```
YS
```
예제 2
입력
```
2
3 3
1
0
3
012
3
012
2
22
```
예상 출력
```
Y
S
```