ECOO '19 R3 P2 - Array Game

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 512M

Problem types

Alice and Bob have recently received a wonderful gift: a sorted array of positive integers! They have decided to create a new game using the array.

Starting with Alice, they take turns picking a positive element of the array and decreasing it by an arbitrary, non-zero amount. If a player cannot make a move on their turn, they lose. To make the game harder, they have also added the restriction that at the end of each player's turn, the array must still be sorted in non-decreasing order.

Alice and Bob have been playing this game for hours, but they are not sure if the moves that they are making are optimal. Hence, they have asked you to analyze their games and see who should have won if both players played optimally.

Input Specification

The input will contain 10 datasets. Each dataset begins with an integer T (1 \le T \le 5), the number of games they wish to analyze. T game descriptions follow. Each game description consists of two lines. The first line contains an integer N (1 \le N \le 16), the number of elements in the array. The next line contains N integers A_i (1 \le A_i \le 10), the original array. The array is guaranteed to be sorted in non-decreasing order.

For the first 3 datasets, N, A_i \le 5.

For the first 6 datasets, N \le 5.

Output Specification

For each dataset, output a string of length T. The i-th character should be A if Alice should have won that game or B if Bob should have won that game.

Sample Input (Two Datasets Shown)

1
1
2
2
3
1 1 1
2
2 2

Sample Output

A
AB

Explanation of Sample Datasets

In the first dataset, Alice can win the game by decreasing the single array value to zero. In the second dataset, the only valid move in each turn of the first game is to decrease the left-most 1 to zero. Since there are an odd number of terms, Alice will win. In the second game, Alice must decrease the first element. If Alice decreases it to zero, Bob can decrease the other element to a zero. If Alice decreases it to 1, Bob can decrease the second element to 1, which is a winning position for him.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.