소 체커
시간 제한1초메모리 제한128 MB
큰 판의 각 시작 칸에 대해 왼쪽이나 아래로만 이동하는 두 사람 게임의 승자를 판정한다.
문제
어느 날 Bessie는 Farmer John에게 '소 체커(Cow Checkers)' 게임을 하자고 도전한다. 이 게임은 크기의 체커판 위에서 진행되며 (, ), 처음에는 좌표 (, )에 체커 말 하나가 놓여 있다. 체커판의 가장 왼쪽 아래 칸의 좌표는 이고, 가장 오른쪽 위 칸의 좌표는 이다. 항상 Bessie가 먼저 움직이며, 그다음부터 두 사람이 번갈아 차례를 진행한다.
각 차례에는 다음 세 종류의 이동 중 하나를 한다.
- 말을 같은 행에서 현재 위치보다 왼쪽에 있는 임의의 칸으로 옮긴다.
- 말을 같은 열에서 현재 위치보다 아래쪽에 있는 임의의 칸으로 옮긴다.
- 말을 현재 칸에서 아래로 칸, 왼쪽으로 칸 떨어진 칸으로 옮긴다. 여기서 는 이동한 위치가 여전히 체커판 안에 있도록 하는 임의의 양의 정수이다.
더 이상 움직일 수 없는(즉, 말이 에 있는) 플레이어가 진다. Bessie가 항상 먼저 시작하고 두 사람 모두 최적으로 플레이한다고 할 때, 누가 이기는지 판별하라.
개의 게임 ()에 대해, 각 게임마다 새로운 시작 좌표 를 읽어 승자를 결정한다.
입력
- 첫째 줄: 공백으로 구분된 두 정수 과
- 둘째 줄: 정수 하나
- 셋째 줄부터 째 줄까지: 각 줄에 공백으로 구분된 두 정수 와
출력
각 게임마다 한 줄씩, 그 게임의 승자에 따라 Farmer John 또는 Bessie를 출력한다. 총 줄을 출력한다.
힌트
체커판에서 말이 처음에 (판의 중앙)에 놓인 하나의 게임을 생각하자.
Bessie는 처음에 말을 , , 또는 으로만 옮길 수 있다. Bessie는 말을 으로 옮겨 즉시 이길 수 있다.