USACO Palindrome Game Problem

This article discusses the Palindrome Game problem in the USA Computing Olympiad (USACO) Bronze Division February 2024 contest, and contains the Python code solution. This problem was posted in analysis mode on the USACO website on February 26, 2024.

USACO Palindrome Game problem

Palindrome Game problem

The Palindrome Game problem was one of the three problems in the USACO Bronze Division February 2024 contest. The February contests may generally be harder than the December and January contests. The programming language we will use in this blog post is Python.

You can read the Palindrome Game problem. Please read and understand the problem first. If necessary, read it may times. Then, write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a flowchart diagram.

Bessie and Elsie will take turns starting with Bessie. Each cow can pick up x stones where x is a positive palindrome integer. The cow who has picked up the last stones wins.

Test Input

This is the test input on the USACO problem page. You can either save the contents of the input into a .in file palindrome_game_1.in or copy-paste it on the Terminal when running the program and it waits for your input.

This is the test output file palindrome_game_1.out.

INPUT

3
8
10
12

OUTPUT

B
E
B

Programming Solution Logic

When Bessie and Elsie have their turns, they play to win. Hence the turn optimal play. If Bessie can play smart and pick up the right number of stones so that Elsie cannot pick up all the remaining stones, and Bessie ends up picking the last stones, that is optimal play.

Let us look at palindrome numbers. Palindrome numbers are 1 through 9, and then 11, 22, 33, and so on, and then 111, 121, 131, and so on.

If there are 1 through 9 stones, Bessie will pick them all up because single-digit numbers are palindrome numbers. Bessie wins.

If there are 10 stones, these are the possible scenarios:

• Bessie picks 1 stone, Elsie picks up the remaining 9. Elsie wins
• Bessie picks 2 stones, Elsie picks up the remaining 8. Elsie wins.
• Bessie can pick up any stone between 1 and 9. Elsie will always win.

If there are 11 stones, these are the possible scenarios:

• Bessie picks up 1 stone, Elsie can pick any of 1-9 stones and they go back and forth. Bessie can always win.

If there are 12 stones, these are the possible scenarios:

• Bessie picks up 1 stone, Elsie can pick any of 1-9 stones. Bessie can always win.

If there are 13 stones, these are the possible scenarios:

• Bessie picks up 1 stone, Elsie can pick any of 1-9 or 11 stones. Bessie can always win.

...

If there are 19 stones, these are the possible scenarios:

• Bessie picks up 9 stones, Elsie can pick any of 1-9 stones. Bessie picks the remaining and always wins.

If there are 20 stones, these are the possible scenarios:

• Bessie picks up 9 stones, Elsie can pick any of 1-9 stones. Bessie picks the remaining, but Elsie always wins.

Drawing this in a tabular form, we get:

We observe that Elsie wins when there are stones which are multiples of 10, that is 10, 20, 30 and so on.

In order to complete this problem, Bessie wins if the number of stones is between 1 and 9. If the number of stones is greater than 9, then Bessie wins if the number of stones is not divisible by 10. In all other cases, Elsie wins.

Analyzing the problem with input

The first line is T, the number of test cases. We will convert it to an int.

The next T lines represent the number of stones in each test cases. We convert each to an int and call it S.

If S is between 1 and 9, output is B.

If S is greater than or equal to 10 and divisible by 10, output is E otherwise B.

My Python solution

This is my Python solution:

t = int(input())

for _ in range(t):
    s = int(input())
    if 1 <= s <= 9:
        print('B')
    elif s % 10 == 0:
        print('E')
    else:
        print('B')

The code is straightforward. Accept the input, check for number value between and including 1 and 9 to declare B the winner, for modulo 10 to declare E the winner and B the winner in all other cases.

Running the Python code

Run the Python code from your Terminal. If you are running it without an input file, you have to manually enter the input.

$ python palindrome_game.py
3
8
10
12

cat INPUT | python PROGRAM

If you are running it by piping it from an input file palindrome_game_1.in

$ cat palindrome_game_1.in | python palindrome_game.py
B
E
B

< INPUT python PROGRAM

$ < palindrome_game_1.in python palindrome_game.py
B
E
B

The output is the same in all three cases.

Submit the Python code

Scroll down the USACO problem page and submit your code. Make sure you change the language to Python 3.6.9 and click on Submit Solution. It will take a few seconds to grade your solution.

Conclusion

If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.

Related Posts

If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.