USACO 2024 February Contest Bronze Division - Palindrome Game

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

By analyzing the brute force we can observe that \(1\) to \(19\) are all winning states for Bessie while \(10\) and \(20\) are the winning states for Elsie.

We can conclude that for a given number \(x\), Bessie can go to a multiple of \(10\) and that would be a losing state. Therefore, we just need to check if the string is a multiple of \(10\) or not to determine the winner.

However, the intuition to get there is more difficult, so the right strategy for a problem like this is to either write a brute force or just observe this through some casework.

Source codes

The source codes in C++ and Python can be seen below.

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int t;
    cin >> t;

    for(; t; t--)
    {
        string s;
        cin >> s;

        cout << (s.back() == '0' ? "E" : "B") << '\n';
    }

    return 0;
}

t = int(input())

for _ in range(t):
    s = input()
    if s[-1] == '0':
        print('E')
    else:
        print('B')