Lynbrook Computer Science

In today’s meeting, we gave a brief introduction to artificial intelligence and some of its many applications, and also introduced a new Problem of the Week, which is as follows:

In an effort to swindle his cows, Farmer John has devised a (not so) brilliant game to play against Bessie. Bessie, compensating for her bovine intelligence, pays you with milk to write a program that helps play for her.
The game begins with n stacks of coins and m_i coins in each stack, and Farmer John graciously lets Bessie go first. If each player takes 1 to k coins from one stack on each turn, and the player who takes the last coin out of all stacks wins, determine who will win assuming optimal play.

For 15 points, solve the problem for n=1 (1 stack of coins).
For 15 more points, solve the problem for 1 < n < 1,000,000
All integers in the input are less than 1,000,000 in magnitude.

Sample Input:
1 2 (one stack, take up to two coins at a time)
6 (the stack has six coins)
Sample Output:
John (either “John” or “Bessie”)

For more sample input/output examples, and a helpful hint, see the meeting slides.

As a reminder, if you haven’t taken USACO yet, you still have until the end of today to take it! Remember, USACO participation counts for 5 points towards your PotW score, so if you have time you really should take it!