라이트 사이클 경주

광선 자전거 경주는 2차원 정사각형 격자의 간선을 따라 달리는 두 대의 오토바이 경기이다. 각 광선 자전거는 지나간 길을 따라 벽을 남긴다. 두 선수는 서로 다른 두 시작점에서 동시에 출발한다. 선수는 다음 세 가지 방식으로 죽을 수 있다. (1) 격자 바깥으로 나갈 때, (2) 벽에 부딪힐 때(자신의 벽이든 상대의 벽이든), (3) 다른 광선 자전거와 충돌할 때.

선수의 경로는 다음과 같이 기술한다. 먼저 선수의 (x, y) 좌표가 주어진다. 처음에 선수는 동쪽, 즉 x축 양의 방향을 바라본다. 경로는 여러 구간으로 이루어지며, 각 구간은 (T, k) 형태이다. T는 회전 방향으로, S(직진), L(왼쪽), R(오른쪽) 중 하나이다. 정수 k는 회전한 뒤 이동할 거리이다. 따라서 "R 6"은 현재 진행 방향에서 오른쪽으로 돌아 6칸 이동한다는 뜻이다.

예를 들어 너비 10, 높이 8인 격자에서 (2, 3)에서 출발하여 "L 4", "R 6", "R 2" 구간을 실행하는 선수를 생각하자. 결과는 그림 1(a)와 같다. 자전거는 1초에 격자 한 칸씩 움직이며, 각 점에 적힌 숫자는 자전거가 그 점에 도달하는 시각이다.

그림 1: 광선 자전거 경로의 예.

프로그램은 주행 영역의 크기와 두 선수의 움직임 설명을 입력받는다. 각 설명에는 선수의 시작 좌표, 움직임 구간의 개수, 구간 목록이 들어 있다. 프로그램은 시각 0에서 게임을 시뮬레이션하며, 다음 중 먼저 일어나는 조건에서 멈춘다. 어느 한 선수가 처음 죽는 시각(두 선수가 동시에 죽을 수도 있다), 또는 두 선수 모두 죽지 않은 상태에서 한 선수가 움직임을 모두 마치는 시각. 게임이 멈추면 프로그램은 종료 시각, 두 선수의 위치, 각 선수가 살아 있는지 죽었는지를 출력한다. 그림 1(b)가 예시이다. 선수는 0번과 1번 두 명이다. 시각 4에 1번이 0번의 벽에 부딪혀 게임이 끝난다. 게임이 끝난 뒤에 주어진 움직임 구간은 무시한다.