Canadian Computing Competition: 2000 Stage 2, Day 1, Problem 3
The game of 31 was a favourite of con artists who rode the railroads in days of yore. The game is played with a deck of cards: four labelled each of 1
, 2
, 3
, 4
, 5
, 6
. (That is, there are four cards labelled 1
, four cards labelled 2
, and so on.) Initially, all of the cards are spread, face up, on a table and the "discard pile" is empty. The players then take turns. During each turn, a player picks up one unused card from the table and lays it on the discard pile. The object of the game is to be the last player to lay a card such that the sum of the cards in the pile does not exceed . Your task is to determine the eventual winner of a partially played game, assuming each player plays the remainder of the game using a perfect strategy.
For example, in the following game player wins:
- Player plays
3
. - Player plays
5
. - Player plays
6
. - Player plays
6
. - Player plays
5
. - Player plays
6
.
Input Specification
The first line of the input is the number of test cases. It is followed by one line for each test case. Each such line consists of a sequence of zero or more digits representing a partially completed game. The first digit is player 's move; the second player 's move; and so on. You are to complete the game using a perfect strategy for both players and to determine who wins.
Output Specification
For each game, output A
or B
on a single line to indicate the eventual winner of the game.
Sample Input
5
356656
35665
3566
111126666
552525
Sample Output
B
B
A
A
A
Comments
Since the last test case was malformed, it was corrected, and all submissions were rejudged.