Deceit in Oceanic Wars!
Johnny loves to play “Oceanic Wars” and so much is his love for the game that he will do anything to win over his opponent, including deceit! He wins every time he plays this game with any opponent as he is a big-time cheater. “Oceanic Wars” is a two-player game played on a 12 by 12 crisscross with rows labeled 1 to 12 and columns labeled A to L. Each player places his/her six ocean-liners on the crisscross. The ocean-liner sizes are 6, 5, 5, 4, 3 and 2 squares long, and they must be placed either horizontally or vertically but not diagonally. The crisscross below shows how Johnny has arranged his liners in one of his games:
The objective of the game is to submerge your opponents’ liners by attacking various crisscross-square locations. When you announce the crisscross-square you are attacking, your opponent tells you whether it was “strike” if one of his liners was on that square or a “float” if none of his liners were on that square.
Using the above example, if Johnny’s opponent attacked crisscross square 5C, a truthful player would declare that it was a “strike”, but not Johnny! He would simply move his liner to a new location that was not attacked till now and respond that it was a “float”! Remember Johnny wants to win at any cost; therefore he follows each attack made by his opponent, and continuously moves his liners to locations which have not been attacked till now. In the above example, he could move the liner one row up or down, but not two rows down since that would bump into another liner (though he could then move that liner) and not one column to the left, since his liner will still lie on 5C. If his opponent had previously attacked 5I, then Johnny could not move his liner one column over to the right either. Remember, Johnny can move any of his liner either horizontal or vertical in order to place it in a safe place!
Your objective in this problem is to assist Johnny in ascertaining if he can still place all his liners after each attack on a crisscross whose initial configuration looks like the above figure and output the attack sequence in case he is unable to place one or more of his liners.
Input
The input file will contain multiple test cases and each test case will contain multiple attacks to various crisscross locations. Input for each test case consist of a single line of the form m K1 K2 K3 . . . Km (0<m<144) where m is the number of crisscross squares which will be attacked and K1, K2, … , Km are the crisscross locations (m, K1, K2 etc,. each are separated by one whitespace). Each location (e.g., K2) will consist of two parts (without any space between them): a number (numbers 1 to 12) indicating the row and an uppercase letter (A to L), indicating the column. The end of all test cases (and hence, the input itself) is signified by m having a value of 0. No invalid inputs would be provided. The test cases are not related to one another; this means that for each test case, your initial configuration of liners would be the same as the figure given above.
Output
For each test case, output one of the following (without any extra white spaces or special characters before or after):
• The number 0 if Johnny can still place his liners after all the attacks in that test case
• The attack sequence number of that test case at which Johnny is unable to place one or more of his liners
An example of multiple test cases
Input Output
15 1J 5A 2D 2I 4B 3C 1E 10A 7D 9B 6E 5F 4G 8C 3H
26 5A 4B 3C 2D 1E 10A 9B 8C 7D 6E 5F 4G 3H 2I 1J 12E 11F 10G 9H 8I 7J 6K 5L 12K 11L 7G
0 0
25
• In the above example, there are two test cases; the first test case has 15 attacks whereas the second test case has 26 attacks.
• In the first test case, even after all the 15 attacks, Johnny is able to place all his liners successfully and hence, the output is zero (0).
• In the second case, there are 26 attacks done by his opponent. However, at the end of the 25th attack (i.e., when 11L is called by the opponent), Johnny finds it impossible to place one of his liners (the liner that is 6 squares long). Hence the output of this test case is 25.