2005 Canadian Computing Competition, Stage 2

Day 2, Problem 2: Segments

You are to find the length of the shortest path from the top to the bottom of a grid covering specified points along the way.

More precisely, you are given an n by n grid, rows 1..n and columns 1..n (1 ≤ n ≤ 20000).

On each row i, two points L(i) and R(i) are given where 1 ≤ L(i) ≤ R(i) ≤ n. You are to find the shortest distance from position (1, 1), to (n, n) that visits all of the given segments in order. In particular, for each row i, all the points

(i, L(i)), (i, L(i) + 1), (i, L(i) + 2), ..., (i, R(i))

must be visited. Notice that one step is taken when dropping down between consecutive rows. Note that you can only move left, right and down (you cannot move up a level). On finishing the segment on row n, you are to go to position (n, n), if not already there. The total distance covered is then reported.

Input

The first line of input consists of an integer n, the number of rows/columns on the grid. On each of the next n lines, there are two integers L(i) followed by R(i) (where 1 ≤ L(i) ≤ R(i) ≤ n).

Output

The output is one integer, which is the length of the (shortest) path from (1, 1) to (n, n) which covers all intervals L(i), R(i).

Sample Input

6
2 6
3 4
1 3
1 2
3 6
4 5

Sample Output

24

Explanation

Below is a pictoral representation of the input.

1     2     3     4     5     6
.     -------------------------
            -------		
-------------
-------
            -------------------
                  -------     .

Notice that on the first row, we must traverse 5 units to the right and then drop down one level.
On the second row, we must traverse 3 units to the left and drop down one level.
On the third row, we must traverse 2 units to the left and drop down one level.
On the fourth row, we move 1 unit to the right and then drop down one level.
On the fifth row, we move 4 units to the right and drop down one level.
On the sixth (and final) row, we move 2 units left, then 2 units right.
In total, we have moved 6 + 4 + 3 + 2 + 5 + 4 = 24 units.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 23, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)