아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

소 체커

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

요약
큰 판의 각 시작 칸에 대해 왼쪽이나 아래로만 이동하는 두 사람 게임의 승자를 판정한다.
난이도

보통10점 중 7점

유형
게임 이론, 수학
정답자
아직 제출이 없습니다

문제

어느 날 Bessie는 Farmer John에게 '소 체커(Cow Checkers)' 게임을 하자고 도전한다. 이 게임은 M×NM \times N 크기의 체커판 위에서 진행되며 (1≤M≤1,000,0001 \le M \le 1{,}000{,}000, 1≤N≤1,000,0001 \le N \le 1{,}000{,}000), 처음에는 좌표 (X,Y)(X, Y) (0≤X<M0 \le X < M, 0≤Y<N0 \le Y < N)에 체커 말 하나가 놓여 있다. 체커판의 가장 왼쪽 아래 칸의 좌표는 (0,0)(0, 0)이고, 가장 오른쪽 위 칸의 좌표는 (M−1,N−1)(M-1, N-1)이다. 항상 Bessie가 먼저 움직이며, 그다음부터 두 사람이 번갈아 차례를 진행한다.

각 차례에는 다음 세 종류의 이동 중 하나를 한다.

  1. 말을 같은 행에서 현재 위치보다 왼쪽에 있는 임의의 칸으로 옮긴다.
  2. 말을 같은 열에서 현재 위치보다 아래쪽에 있는 임의의 칸으로 옮긴다.
  3. 말을 현재 칸에서 아래로 kk칸, 왼쪽으로 kk칸 떨어진 칸으로 옮긴다. 여기서 kk는 이동한 위치가 여전히 체커판 안에 있도록 하는 임의의 양의 정수이다.

더 이상 움직일 수 없는(즉, 말이 (0,0)(0, 0)에 있는) 플레이어가 진다. Bessie가 항상 먼저 시작하고 두 사람 모두 최적으로 플레이한다고 할 때, 누가 이기는지 판별하라.

TT개의 게임 (1≤T≤1,0001 \le T \le 1{,}000)에 대해, 각 게임마다 새로운 시작 좌표 X,YX, Y를 읽어 승자를 결정한다.

입력

  • 첫째 줄: 공백으로 구분된 두 정수 MM과 NN
  • 둘째 줄: 정수 TT 하나
  • 셋째 줄부터 T+2T+2째 줄까지: 각 줄에 공백으로 구분된 두 정수 XX와 YY

출력

각 게임마다 한 줄씩, 그 게임의 승자에 따라 Farmer John 또는 Bessie를 출력한다. 총 TT줄을 출력한다.

힌트

3×33 \times 3 체커판에서 말이 처음에 (1,1)(1, 1)(판의 중앙)에 놓인 하나의 게임을 생각하자.

Bessie는 처음에 말을 (1,0)(1, 0), (0,1)(0, 1), 또는 (0,0)(0, 0)으로만 옮길 수 있다. Bessie는 말을 (0,0)(0, 0)으로 옮겨 즉시 이길 수 있다.

예제3

  1. 예제 1

    입력
    3 3
    1
    1 1
    
    예상 출력
    Bessie
    
  2. 예제 2

    입력
    10 10
    1
    1 2
    
    예상 출력
    Farmer John
    
  3. 예제 3

    입력
    1 1
    1
    0 0
    
    예상 출력
    Farmer John