DWITE '11 R4 #4 - Lego Ladder

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE, January 2012, Problem 4

Little Alice and Little Bob are playing with their favourite toys, Lego blocks. They have 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 (1 \le N \le 15), the number of blocks in that game. The next line contains N space-separated integers, representing the heights of the blocks, which will be integers from 0 to 100 inclusive.

The output will contain 5 lines, with strings of 3 characters each. The ith character of the jth line should represent the result of the ith game of the jth test case: A if Little Alice wins, and B if Little Bob wins.

Sample Input

2 3
0 2 2
1 2 4 3

Sample Output


Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


  • 4
    Arman_Lamei  commented on July 31, 2019, 1:43 p.m.

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