NOI '14 P3 - Deletion Game

View as PDF

Points: 30 (partial)
Time limit: 4.5s
Memory limit: 512M

Problem type
National Olympiad in Informatics, China, 2014

Recently, little Z has been addicted to a new type of deletion game. This game takes place on an grid. Initially, the grid cells are filled with integers from to . Through deletion, the cells become blank (denoted by ). We will denote the cell at row , column as , and let its coordinates be .

Given three parameters , , and , the player can make no greater than moves. For each move, the player must first find a path of length in the grid. Formally, this path is represented by two length sequences and that satisfy the following conditions:

1. and , where , meaning that is a valid cell on the grid.
2. where , meaning that and are two neighbouring cells on the grid.
3. or , where , meaning that the path does not repeat cells.
4. , where , meaning that the path does not go through any blank cells.
5. , meaning that the path does not start with the number .
6. , meaning that the length of the path has to fall within the given range.

Then, the player will string the digits on the path together into an integer . Formally:

The game will provide two parameters and to calculate the player's score on a move:

1. If is a prime number, then the prime subscore is , otherwise the prime subscore is .
2. If is a palindromic number (i.e. when viewed as a string, is identical whether its letters are arranged forwards or reverse), then the palindromic subscore is , otherwise the palindromic subscore is .
3. If the prime subscore and the palindromic subscore are both equal to , then the overall score for the move is . Otherwise, the overall score for the move is equal to the sum of the prime subscore and the palindromic subscore.

If after a move the move's overall score is , then you will have wasted the move and the game's state will not change. Otherwise, if the move's overall score is greater than , then all cells on the path will be set to blank, and the cells above the blank will drop down. Formally, the following operations take place:

1. Set , where .
2. Examine every cell in the grid. If a cell satisfies , , and , then set and . Repeat this step until no more cells in the grid satisfy the conditions.

The following is an example of a player making a move and deleting some cells. In this case, and . The player starts off facing the board in figure 1.

1. The player selects the path containing digits and , which strung together makes . Since is a prime number, the prime subscore is . Since is not a palindromic number, the palindromic subscore is . Thus, the overall score for the move is .
2. Since the score of the move is nonzero, the path's values are deleted (as in figure 2).
3. Digits above the blank cells drop down (as in figure 3). At this point, the player is ready to make the next move.

We will also give you a parameter . After the player has made every move, the player's final score will be determined using . If , then the player's final score is equal to the sum of the scores across every move. If , then the player's final score will be sum of the scores across every move, divided by , rounded down. Formally:

where is the final number of non-blank cells at the end of the game.

Little Z finds himself hooked to this game, unable to step away. She would like your help. For the given parameters, provide a series of moves to play the game. Of course, the final score should be as high as possible.

Input Specification

There will be 10 files game1.in ~ game10.in that will be given to your program (through standard input). They can be downloaded here for you to study: game.zip.

For each test case:

The first line of input will contain an integer from to , representing the test case number. Test case gamei.in will have on its first line.
The second line of input will contain eight space-separated integers , , , , , , , and .
The next lines will each contain integers, representing the array . Adjacent integers on the same line will be separated by a space.
The input will not contain any extra or trailing spaces.

Output Specification

The first line of output should contain a single integer , representing the number of moves you would like to make.
lines should follow, each describing one move. For each of these lines, the first integer should be , representing the length of the path. integers should follow on the same line. They are, respectively, .
The output should not contain extra spaces or lines. Adjacent values on the same line should be separated by a single space.
Your output should not exceed 1MB in size. The data guarantees that a valid answer will not exceed this upper bound.

Sample Input 1

0
3 3 100 2 3 1 1 0
2 1 1
2 3 3
4 7 1

Sample Output 1

4
2 2 2 3 2
2 3 1 3 2
2 2 1 3 1
3 1 3 2 3 3 3

Explanation 1

Four deletions are made. The deleted paths and move scores are, respectively: (for a score of ), (for a score of ), (for a score of ), and (for a score of ). Since , the final score is simply . There may exist a more optimal solution.

Sample Input 2

0
1 3 100 2 3 1 1 1
2 1 1

Sample Output 2

1
2 1 2 1 3

Explanation 2

Only one deletion is made. The deleted path is . The score is . Since , the final score is equal to , the sum of scores across all moves, divided by , rounded down, which is . If the deleted path was , then an optimal final score of 4 would have been obtained.

For each test case, we have set up 9 parameters . If your output is invalid, then your score will be for the test case. Otherwise, assuming your final score is , then your score out of 10 for the test case will be given by the following table.

Score Condition
10
9
8
7
6
5
4
3
2
1

Experimentation

We provide a tool game_check (GNU/Linux: game_check, Windows: game_check.exe) for you to help check if your output program is valid. The usage for this program (on Windows) is:

game_check.exe <case_no>

where <case_no> is the number of the test case. For example:

game_check.exe 3

will test game3.out to determine whether it is accepted.

After you invoke this program, the checker will provide the result to the execution of your output file in one of the following ways:

• Abnormal termination: An unknown error occurred.
• Input/Output file does not exist.: We cannot load your input or output file.
• Output invalid!: There is an error with your output file. A general error message may now be included.
• Details: xxx.: Other information.
• Correct! Your answer is x.: Your output is acceptable. Your final score is .

Note from admin: Please ensure that both the input file gameX.in and output file gameX.out are present and correctly formatted when you run the program. Note that the first integer in the input file is the test case number , and will be ignored. Furthermore, this program is only guaranteed to work on the dataset provided in the zip file above. Running the program on your own input is not guaranteed to yield the correct results.

Problem translated to English by Alex.