### 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)

It's quiet in here...