Making a Mandal-art
Time limit1sMemory limit1024 MB
Given a 9x9 mandal-art grid, print each intermediate goal with its 8 detailed goals, sorted lexicographically at both levels.
- Level
Easy3 of 10
- Topics
- Implementation, Sorting, String
- Solved
- No attempts yet
Problem
Uju decided to make a New Year plan using a mandal-art.
A mandal-art is a table made by arranging 3x3 matrices, three across and three down, into a 9x9 matrix. To make one, first create goals as follows.
- Create 1 final goal.
- Create 8 intermediate goals that help achieve the final goal.
- For each intermediate goal, create 8 detailed goals that help achieve it.
Use these goals to build the mandal-art as follows.
- Divide the 9x9 matrix into nine 3x3 matrices.
- Fill the 3x3 matrix at the center of the 9x9 matrix. Write the final goal in the exact center, and write the 8 intermediate goals one each in the remaining 8 cells.
- Write the intermediate goals again in the center of each of the other 3x3 matrices, excluding the central 3x3 matrix. The direction in which an intermediate goal sits within the central 3x3 matrix must match the direction of the 3x3 matrix centered on that same intermediate goal within the 9x9 matrix. For example, if the intermediate goal "health" is written in the upper right of the final goal in the central 3x3 matrix, the 3x3 matrix centered on "health" must be in the upper right of the 9x9 matrix.
- Fill the blank cells of each 3x3 matrix with detailed goals. Write 8 detailed goals, one each in the 8 cells, that help achieve the intermediate goal in the center.
Nobody recognized the plan Uju made, so Uju decided to write the mandal-art in a simpler form. The simplified plan is made as follows. First, print one intermediate goal, followed by its 8 detailed goals below it. Repeat this 8 times to print all 8 intermediate goals with their detailed goals. Intermediate goals must be sorted in lexicographic order, and the 8 detailed goals under each intermediate goal must also be sorted in lexicographic order. Goal a comes before goal b in lexicographic order in the following cases.
- Digits come before letters.
- Uppercase letters come before lowercase letters.
- Given goals of length i and i+1 whose characters from index 0 through index i are identical, the goal of length i comes first. For example, "ab" comes before "abc".
Input
The input has 9 lines containing a 9x9 mandal-art. Only valid mandal-arts are given. A valid mandal-art satisfies the following conditions.
- The center 3x3 matrix of the 9x9 matrix contains the final goal and the intermediate goals.
- The direction in which the intermediate goals are written in the central 3x3 matrix matches the direction in the other 3x3 matrices.
- No goal appears twice. However, each intermediate goal appears twice in the matrix in total.
All goals consist of English lowercase letters, uppercase letters, and digits. Each goal is no longer than 100 characters. Different goals are separated by spaces, and no goal contains a space.
Output
On the first line, print "#x. " followed by the intermediate goal that comes first in lexicographic order. Digits come before letters, and uppercase letters come before lowercase letters. From the second line on, print "#x-y. " followed by a detailed goal, in sorted order, on each of the next 8 lines. Repeat the process of one intermediate goal line followed by 8 detailed goal lines 8 times. x and y start at 1 and increase by one each time.
The final goal is not printed.