Task 5 will be revealed 18.10.2024 at 18:00 CET
Login required
*
Available from 18.10.2024 18:00 CET until 19.10.2024 17:59 CET - You can get 5 points
*
CCTV
Security in the Mercadona shopping center is ensured using a video surveillance system.
The security guard has a program open on his computer that displays video streams from several cameras. This program is structured as follows: a rectangular grid consisting of h rows and w columns is presented on the screen. Each cell can be empty, or an image from one of the cameras is displayed there. To control the location of images in the program, the security officer can use the left, right, up and down buttons.
The left button moves the image from each cell to the cell to the left of it. This moves the image from the leftmost cell in each row to the rightmost cell in that row.
The “right”, “up” and “down” buttons operate in a similar way. The right button moves the image from each cell to the cell to the right of it. The images in the rightmost cell in each row are moved to the leftmost cell in that row. The up button moves the image from each cell to the cell above it. Images from the topmost row are moved to the cells in the bottom row. The down button moves the image from each cell to the cell below it. Images from the bottom row are moved to cells in the top row.
Rows in the grid are numbered from top to bottom, columns are numbered from left to right. The cell at the intersection of row number r and column number c is designated as (r, c).
Below is a grid with 3 rows, 4 columns and three cells containing images, with coordinates (1, 1), (2, 4) and (3, 3). It also shows where these images will go when you click on each of the four buttons.
It is more convenient for the security guard that the cells on the monitor that contain the images from the cameras are located as compactly as possible. The compactness of images is the minimum area of the grid subrectangle that contains all displayed images. Note that using the buttons you can change the compactness. For example, the left side of the figure below shows an image layout that has a compactness of 12. If you press the right button once and press the up button once, the image compactness becomes 4.
You are given a grid that contains k cells with images. Calculate the minimum compactness that can be achieved using the left, right, up and down buttons, as well as the minimum number of button presses required. In the example above correct answer is “2 moves, compactness is 4”.
Of course, you can solve the problem by completely searching through all the options, but you need to find a more optimal solution.
Input format
The first line contains three integers h, w, and k — the grid sizes and the number of cells with the image.
Each of the next k lines contains two integers ri and ci — the coordinates of the cell containing the image (1 ⩽ ri ⩽ h; 1 ⩽ ci ⩽ w). It is guaranteed that all k cells are different.
Output format
Print two integers — the minimum compactness of the image arrangement that can be achieved using buttons, and the minimum number of button presses required to achieve this compactness.
Example (from the story above):
Input:
Height; Width; Number of active cells
3; 4; 3
Coordinates
1; 4
3; 1
3; 4
Output (compactness; moves):
4; 2
Your task
Read input file with 2 cases and into the field with the answer, enter :
- the resulting values for each case
- the country, which description refers to
- and the source code of your program.
Click here to download the Task 5 Input File
~~~~~~~~~~~~~~~~~~~~~~~~
Answer
4; 2
6; 0
Spain
|
Points |
Correct answer |
Country |
Source Code |
|
Round 1 |
1 |
1 |
1 |
|
Round 2 |
2 |
1 |
1 |
|
Round 3 |
3 |
1 |
1 |
|
Round 4 |
4 |
1 |
1 |
|
Round 5 |
5 |
1 |
1 |
|
|
||||||||||||||||||
|
Bonus points |
Quick and correct answer |
|
||||||||||||||||
|
Round 1 |
5 |
4 |
3 |
2 |
1 |
|||||||||||||
|
Round 2 |
||||||||||||||||||
|
Round 3 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|||||||||||
|
Round 4 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
||||||||||
|
Round 5 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|||||||||