Canadian Computing Competition: 2004 Stage 2, Day 2, Problem 2
Jenga is a popular game involving a tower constructed of ~1\times1\times3~ blocks. Initially, this tower has ~18~ levels, each consisting of three blocks laid side to side. The blocks on alternating levels are oriented at right angles. Thus, each block touches all three of the blocks in the levels above and below it. Here is a picture of the actual game:
Play involves each player removing a block from somewhere in the tower, and putting it in a new position on top. The goal is to do this without knocking over the tower. Blocks are always removed from below the highest complete level, and the top level is always completed before a new level is started (at right angles, of course).
Write a program which reads sequential moves of a Jenga game and determines at what point the tower (or any part of it) falls or topples.
Note that a structure will topple if its center of gravity, projected onto its base, lies outside the convex hull of its support points. If the center of gravity lies exactly on the edge of this hull, we will assume that the structure is stable.
The first line contains ~N~, the number of moves. The next ~N~ lines describe one move per
line, with two locations separated by a single space. The first is the location of the block to
be removed, and the second is where it will be put back. A location is specified as a number,
specifying the level, and then a letter
A-C, specifying its position in the level (left to right or
front to back). For instance, the top level of the initial tower configuration consists of blocks
18C. Below is a diagram of the pieces, labelled with a front and right side
If the tower collapses after removing a block at location ~L~, output
The tower collapses
after removing L.
If the tower collapses after placing a block at location ~L~, output
The tower collapses
after placing L.
If all moves execute successfully (i.e., without causing the tower to fall), output
tower never collapses.
Sample Input 1
4 6B 19B 7B 19A 17B 19C 17A 20B
Sample Output 1
The tower collapses after removing 17A
Sample Input 2
2 17C 19C 17A 19A
Sample Output 2
The tower never collapses