DWITE '11 R4 #4 - Lego Ladder - DMOJ: Modern Online Judge

DWITE '11 R4 #4 - Lego Ladder

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 64M

Problem type

DWITE, January 2012, Problem 4

Little Alice and Little Bob are playing with their favourite toys, Lego blocks. They have $N$ $N$ blocks of various heights, arranged in a row. They decide to play a game with their blocks.

Alice and Bob take turns removing one Lego block from the row, with Alice going first. At the beginning of a player's turn, if the blocks form a ladder – a sequence of either non-increasing or non-decreasing heights – that player loses. Given the heights of the initial row of blocks, determine who has the winning strategy, if they play optimally.

The input will contain 5 test cases, and each test case describes 3 games. The first line of each game contains a number $N$ $N$ ( $1 \le N \le 15$ $1 \leq N \leq 15$ ), the number of blocks in that game. The next line contains $N$ $N$ space-separated integers, representing the heights of the blocks, which will be integers from $0$ $0$ to $100$ $100$ inclusive.

The output will contain 5 lines, with strings of 3 characters each. The $i^\text{th}$ $i^{th}$ character of the $j^\text{th}$ $j^{th}$ line should represent the result of the $i^\text{th}$ $i^{th}$ game of the $j^\text{th}$ $j^{th}$ test case: A if Little Alice wins, and B if Little Bob wins.

Sample Input

Copy

Sample Output

Copy

BBA

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

-1

ColonelBy_team10 commented on June 6, 2021, 4:08 p.m.

what is a ladder how does a lego make a ladder

3

Arman_Lamei commented on July 31, 2019, 5:43 p.m.

There's a trailing space after one of the n's in the test data.