National Olympiad in Informatics, China, 2002
Yuan Yuan is getting tired of the traditional game of Tetris, so she has decided to create a new set of rules. The game takes place on an infinitely-tall grid of columns, where the columns of the grid from left to right are labeled from to . In this game, the player uses the types of tiles depicted in figure . Every such tile is made up of exactly four smaller squares. The picture contains the numberings of the tiles .
The rules of the game are as follows:
- To describe the status of the grid: Every possible state of the grid in the game is described using the number of consecutive squares in each column. For example in figure , the grid contains columns. Column contains small squares. Column contains two small squares. Column contains small squares. Column contains small squares. Therefore, we can use the -tuple to describe this grid state.
- The game initially selects a tile and drops it into a specified column . The command is described by the pair . That is, the leftmost squares(s) of tile number is lined up with column and dropped. An example is depicted in figure , where tile number is placed in column , representing the command . The tile continues to fall until it reaches the bottom of the grid, immediately creating the game state . However since the bottom two rows are filled completely, the rules will make these two rows automatically vanish, reaching the state depicted in figure , denoted by .
- The game ends when the number of squares in all the columns are . For example when tile number is selected and dropped in the leftmost column of the grid in figure using the command , the immediate game state would become . The two entire rows vanish after being filled, resulting in the game state , finally successfully ending the game.
- The rules require that tiles never occupy regions outside of the bounds of the grid. For example, in figure where , the command will be out of bounds.
- The rules require that no tiles may produce "floating" squares. A floating square is a square positioned such that not all of the squares in its column are consecutive. Figure is one such situation. For example, in the grid for figure , the commands , , and are all illegal.
Although the ability to pick which tiles drop greatly simplifies the game, completely getting rid of all the squares still remains a very annoying task. Would you like to try?
The first line of input contains an integer , the number of columns. The second line contains integers, representing the initial state of the grid. Each integer on this line represents the number of consecutive squares are in the corresponding column.
The output should contain many lines of commands. Each line should contain two integers and , separated by a space. It is guaranteed that there is a solution, although not necessarily unique. You may output any such solution.
4 3 2 3 0
1 4 9 1
For each test case, your score out of will be:
- , if your output is incorrect or the number of commands exceeds .
- , if your output is correct but the number of commands exceeds .
- , if your output is correct and the number of commands does not exceed .