시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 171 | 84 | 76 | 60.800% |
Mr. JOI has a huge desk in his collection room, and there are a number of rare coins on it. To clean up the desk, he is going to rearrange the coins.
The desk can be regarded as a 2 000 000 001 × 2 000 000 001 grid. The columns are numbered from −1 000 000 000 through 1 000 000 000 from left to right, and the rows are numbered from −1 000 000 000 through 1 000 000 000 from bottom to top. The cell with the column number x and the row number y is denoted by (x, y).
There are 2N coins. Currently, the i-th coin (1 ≤ i ≤ 2N) is placed at the cell (Xi, Yi). Mr. JOI’s goal is to place a coin on each cell (x, y) with 1 ≤ x ≤ N and 1 ≤ y ≤ 2. In order not to hurt the coins, the only operation he can perform is to choose a coin and move it to one of the neighboring cells (a cell neighbors another if and only if they share an edge). It is allowed that multiple coins are placed on a cell at some point. He wants to achieve the goal with as few operations as possible.
Write a program which, given the number of coins and the cells where the coins are currently placed, calculates the minimum number of operations needed to achieve the goal.
Read the following data from the standard input.
N X1 Y1 . . . X2N Y2N
Write one line to the standard output. The output should contain the minimum number of operations needed to achieve the goal.
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | N ≤ 10. |
2 | 29 | N ≤ 1 000. |
3 | 63 | No additional constraints. |
3 0 0 0 4 4 0 2 1 2 5 -1 1
15
In this sample input, 6 coins are placed as the figure below. The goal is to collect the coins inside the thick lines.
For example, Mr. JOI can achieve the goal with 15 operations by the following moves:
As he cannot achieve the goal with 14 or less operations, you should output 15
4 2 1 2 1 2 1 3 1 3 1 3 1 3 1 3 1
9
Multiple coins may be placed on a cell.
5 1000000000 1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 -1 -5 -2 2 2 8 4 7 -2 5 7 3
8000000029