|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
In the year of 2018, the International Olympiad in Informatics will be held in Japan. In order to celebrate it, the committee of IOI is planning to make an artwork of “slightly odd design”, and decorate the competition venue with it. The committee requested the JOI (Just Odd Inventions) Co. Ltd. to make a design of it. The designers of JOI proposed the following:
Moreover, they proposed the kinds of tiles for the artwork. However, they did not propose how to pave tiles on the board, which is the most important part of the design. Because the designs proposed by JOI are always beautiful, the committee decided to obey the proposal of JOI for the kinds of the tiles. The committee has to think of the way to pave the tiles on the board. The committee decided to pave the tiles in order to maximize the beauty of the design.
The beauty of the design is calculated as follows:
If two tiles of 1 × 2 shares the edges of two cells, we count the scores of these two edges independently. You are to calculate the way to pave the tiles on the board whose beauty is as large as possible.
Given the size of the board, the size and the color of each tile, and the way to calculate the beauty of the design, determine the way to pave the tiles whose beauty is as large as possible.
There are five subtasks. Each subtask corresponds to a public input data. The format of each input data file is as follows.
Submit an output data file for each input data file. The output data file consists of N lines. The i-th line (1 ≤ i ≤ N) describes the way to put the tile i on the board in the following format.
All input data satisfy the following conditions.
For each subtask, the values of H, W, K, N are as in the following table. For the values of X, Y, see Grading.
|1||7||24||3||168||124 000||130 000|
|2||50||50||80||1 800||3 260 000||3 850 000|
|3||100||100||100||7 200||7 420 000||9 220 000|
|4||100||100||100||7 000||7 150 000||9 000 000|
|5||100||100||100||5 200||11 700 000||13 850 000|
이 문제의 채점은 16775.txt를 사용한다.
3 2 3 4 1 1 2 2 1 3 2 1 2 7 5 7 4 3 5 3 1
2 2 1 1 1 2 3 2 3 1 2 1
In this sample input, the size of the board of the design is 3 × 2, and 4 tiles are used. The color and the size of each tile is as follows:
|1||1||1 × 1|
|2||2||1 × 2|
|3||3||1 × 1|
|4||1||1 × 2|
There is a tile of size 1 × 1 with color 1, a tile of size 1 × 2 with color 2, a tile of size 1 × 1 with color 3, and a tile of size 1 × 2 with color 1.
We put the tiles as follows. The numbers in the figure indicate the numbers of the tiles.
The beauty of the design is calculated as follows. The beauty of the design is 26.