This problem is an example of the classic "game theory" types of problems, which can be viewed as a form of dynamic programming.
Let a square (i, j) be called a "winning position" if it is possible for someone to win when the checker is currently on (i, j) and it is his turn to move. Clearly, (0, 0) is a losing position, and (i, 0), (0, i), and (i, i) are winning positions for all i. More generally, square (i, j) is a winning position if it is possible to transition to a losing position in one move, and it is a losing position if it is not possible to do so. For example, (1, 2) is a losing position because it can only move to (0, 2), (1, 0), and (1, 1), all of which are winning positions.
In this way, we can create a boolean array state[i][j] storing whether a square is winning or losing. This array starts off like this:
x 0 1 2 3 4 5 6 7 8 . . . y 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 1 3 1 1 1 1 1 0 1 1 1 4 1 1 1 1 1 1 1 0 1 5 1 1 1 0 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 7 1 1 1 1 0 1 1 1 1 8 1 1 1 1 1 1 1 1 1 . . . . . .
However, for the given bounds, it would require too much time and memory to create this array.
Instead, we make the following observation: for each diagonal, there exists at most one losing position on that diagonal, so there are at most n+m losing positions. Thus it suffices to track only the losing positions.
We can find these recursively as follows: Consider the current losing position (the first one would be (0, 0) ). Make a "knight's leap" by increasing the x coordinate by 1 and the y coordinate by 2, ensuring that we are now on a different diagonal, and then move along this diagonal until there are no losing positions on the current row or column. For clarity, look at Lewin's solution below:
import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class cowcheck { private static BufferedReader in; private static PrintWriter out; public static void main (String [] args) throws IOException { in = new BufferedReader (new FileReader ("cowcheck.in")); out = new PrintWriter (new BufferedWriter (new FileWriter ("cowcheck.out"))); StringTokenizer st = new StringTokenizer (in.readLine ()); int M = parseInt (st.nextToken ()), N = parseInt (st.nextToken ()); int upper = Math.max (M, N); int cx = 0, cy = 0; int [] xval = new int [upper]; Arrays.fill (xval, -1); int idx = 0; xval [y] = cx; while (true) { cx += 1; cy += 2; while (cy < upper && xval [cx] != -1) { cx++; cy++; } if (cy >= upper) break; xval [cy] = cx; } int T = parseInt (in.readLine ()); for (int i = 0; i < T; i++) { st = new StringTokenizer (in.readLine ()); int x = parseInt (st.nextToken ()), y = parseInt (st.nextToken ()); if (x > y) {y ^= x; x ^= y; y ^= x;} out.println (xval [y] == x ? "Farmer John" : "Bessie"); } out.close (); System.exit (0); } }This game is a variant of the classical game Nim called 'Wythoff's Game'. In Nim, you are given a heap of coins and two players alternate taking up to a certain number of coins until the heap runs out. This game is essentially the same game but with two heaps instead. The observation that the x and y positions of the checker can be decoupled makes it easier to see the connection with Nim. As a final note, it is possible to derive an elegant closed form for the losing positions. It turns out that all positions of the form (floor(k*phi), floor(k*phi^2)), where phi is the golden ratio (i.e. (1 + sqrt(5))/2) and k is any non-negative integer, are the only losing positions that exist. Here is Amlesh's concise code:
#include<iostream> #include<fstream> #include<cmath> #include<set> using namespace std; const double phi = (1 + sqrt(5))/2; int M, N, T, X, Y; set<pair<int, int> > cold; main() { freopen("cowcheck.in", "r", stdin); freopen("cowcheck.out", "w", stdout); cin >> M >> N >> T; for (int n = 0;; n++) { int x_n = floor(n*phi), y_n = floor(n*phi*phi); if (x_n>=M||y_n>=N) break; cold.insert(make_pair(x_n, y_n)); } for (int i = 0; i < T; i++) { cin >> X >> Y; if (cold.find(make_pair(min(X, Y), max(X, Y)))==cold.end()) cout << "Bessie" << endl; else cout << "Farmer John" << endl; } }