National Olympiad in Informatics, China, 2002

Day 2, Problem 2 - New Tetris

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 N (1 ≤ N ≤ 1500) columns, where the columns of the grid from left to right are labeled from 1 to N. In this game, the player uses the 19 types of tiles depicted in figure 1. Every such tile is made up of exactly four smaller squares. The picture contains the numberings of the tiles T (1 ≤ T ≤ 19).

The rules of the game are as follows:

1. 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 2, the grid contains N = 4 columns. Column 1 contains 3 small squares. Column 2 contains two small squares. Column 3 contains 3 small squares. Column 4 contains 0 small squares. Therefore, we can use the 4-tuple (3, 2, 3, 0) to describe this grid state.
2. The game initially selects a tile T (1 ≤ T ≤ 19) and drops it into a specified column C (1 ≤ C ≤ N). The command is described by the pair (T, C). That is, the leftmost squares(s) of tile number T is lined up with column C and dropped. An example is depicted in figure 2, where tile number T = 1 is placed in column C = 4, representing the command (1, 4). The tile continues to fall until it reaches the bottom of the grid, immediately creating the game state (3, 2, 3, 4). However since the bottom two rows are filled completely, the rules will make these two rows automatically vanish, reaching the state depicted in figure 3, denoted by (1, 0, 1, 2).
3. The game ends when the number of squares in all the columns are 0. For example when tile number 9 is selected and dropped in the leftmost column of the grid in figure 3 using the command (9, 1), the immediate game state would become (2, 2, 2, 2). The two entire rows vanish after being filled, resulting in the game state (0, 0, 0, 0), finally successfully ending the game.
4. The rules require that tiles never occupy regions outside of the bounds of the grid. For example, in figure 2 where N = 4, the command (18, 4) will be out of bounds.
5. 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 5 is one such situation. For example, in the grid for figure 2, the commands (2, 1), (17, 2), and (10, 3) 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?

Input Format

The first line of input contains an integer N, the number of columns. The second line contains N integers, representing the the initial state of the grid. Each integer on this line represents the number of consecutive squares are in the corresponding column.

Output Format

The output should contain many lines of commands. Each line should contain two integers T and C, separated by a space. It is guaranteed that there is a solution, although not necessarily unique. You may output any such solution.

Sample Input

4
3 2 3 0

Sample Output

1 4
9 1

Scoring

For each test case, your score out of 10 will be:

• 0, if your output is incorrect or the number of commands exceeds 1,000,000.
• 7, if your output is is correct but the number of commands exceeds 100,000.
• 10, if your output is correct and the number of commands does not exceed 100,000.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 11, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I found the test cases for this question are somewhat weak.
I submitted a partial solution, just for being sure I have the correct direction.
I got 100, although I can generate small test cases that my (partial) solution can't handle, but are solvable with pen and paper.
Admins can see empty switch-case blocks in my code - these are the cases I know about but didn't implemented yet.

The initial number of squares in each column can be up to 1000 (however, in most cases, it's less than 10).