22883번 - 은퇴한 자들의 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 160 | 41 | 34 | 30.357% |
문제
PS계를 성공적으로 은퇴한 제연이와 덕인이는 허전한 마음을 달래기 위해 새로운 보드게임을 개발했다. 이 게임은 $K$개의 판과 $K$개의 말로 구성된다. $i (i=1,\cdots,K)$번째 판은 세로 길이 $N_i$, 가로 길이 $M_i$ 크기의 격자판인데, 게임을 시작하기 전 울타리를 사용해 경계를 만든다.
울타리는 격자의 변을 따라 짓는다. 격자판의 왼쪽 위 꼭짓점에서부터 오른쪽(R) 또는 아래(D)로만 길이 1씩 움직여서 오른쪽 아래 꼭짓점에 도달하는 길이 $N_i + M_i$의 경로들을 고려하자. 이 중 시작점과 끝점을 제외하고는 만나지 않는 두 경로를 골라 이들을 따라 울타리를 지었을 때 이를 좋은 울타리 배치라고 한다.
| (a) | (b) | (c) |
그림 K.1: 좋은 울타리 배치와 나쁜 울타리 배치
예를 들어 $N_i = 5, M_i = 4$인 경우를 살펴보자. (a)의 경우 두 경로 RRDRDDDRD, DDRRDDDRR이 시작점과 끝점을 제외하고는 만나지 않으므로 좋은 울타리 배치이다. 한편 (b)의 경우 선택된 두 경로 RDRDRDRDD, DDRRDDDRR이 시작점도 끝점도 아닌 곳에서 만나므로 좋은 울타리 배치가 아니다. (c)의 경우 두 경로 중 하나가 오른쪽 또는 아래로만 움직이는 경로가 아니므로 마찬가지로 좋은 울타리 배치가 아니다.
게임은 $K$개의 격자판에 각각 좋은 울타리 배치로 경계를 만든 뒤, 각 격자판의 가장 왼쪽 위 칸에 말을 하나씩 놓은 상태로 시작된다. 게임은 제연이가 먼저 시작해 한 턴씩 번갈아 가며 진행된다. 제연이는 자신의 차례에 $K$개의 말 중 하나를 골라 오른쪽으로 한 칸 이동시켜야 하고, 덕인이는 자신의 차례에 $K$개의 말 중 하나를 골라 아래로 한 칸 이동시켜야 한다. 울타리를 넘어서 말을 이동시킬 수는 없으며, 자신의 차례에 움직일 수 있는 말이 없는 사람이 게임에서 지게 된다.
안타깝게도 이 게임은 행운 요소가 하나도 없는 실력겜이라 두 사람이 최선을 다한다면 게임을 하기 전에도 이길 사람을 알 수 있다. 둘은 더 이상 PS 문제를 풀 의지가 남아있지 않기 때문에 여러분이 이길 사람을 알려줘야 한다.
입력
첫째 줄에 정수 $K (1 \leq K)$가 주어진다.
두번째 줄부터 $i=1,\cdots,K$ 번째 격자판의 정보가 각각 세 줄씩 주어진다. 첫째 줄에 정수 $N_i, M_i$가 주어지고, 이후 두 개의 줄에는 울타리를 짓는 두 경로가 각각 길이 $N_i + M_i$의 문자열로 주어진다. 각 문자열은 R 또는 D로만 이루어져 있으며, 좋은 울타리 배치를 표현한다. ($1 \leq N_i,\, 1 \leq M_i,\, \sum_{i=1}^{K} \left(N_i+M_i\right) \leq 500\ 000$)
출력
두 사람이 최선을 다해서 게임을 진행할 때, 제연이가 이기면 First, 덕인이가 이기면 Second를 출력한다.
예제 입력 1
2 3 2 RRDDD DRDDR 1 2 DRR RRD
예제 출력 1
First
예제 입력 2
2 2 2 DRDR RRDD 4 5 RDRDDRRRD DDDRDRRRR
예제 출력 2
Second
노트
그림 K.2: 예제 1 참고
예제 1의 초기 게임판은 위와 같다. 제연이가 첫 번째 턴에 두 번째 판의 말을 오른쪽으로 움직이면 덕인이는 더 이상 말을 움직일 수 없으므로 제연이가 이긴다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호