## CCO '05 P5 - Segments

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Canadian Computing Competition: 2005 Stage 2, Day 2, Problem 2

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 by grid, rows and columns . On each row , two points and are given where . You are to find the shortest distance from position , to that visits all of the given segments in order. In particular, for each row , all the points

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 , you are to go to position , if not already there. The total distance covered is then reported.

#### Input Specification

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

#### Output Specification

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

#### Sample Input

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

#### Sample Output

24

#### Explanation for Sample Output

Below is a pictoral representation of the input.

1       2       3       4       5       6
.       _________________________________
________
_________________
_________
_________________________
_________       .

Notice that on the first row, we must traverse units to the right and then drop down one level.

On the second row, we must traverse units to the left and drop down one level.

On the third row, we must traverse units to the left and drop down one level.

On the fourth row, we move unit to the right and then drop down one level.

On the fifth row, we move units to the right and drop down one level.

On the sixth (and final) row, we move units left, then units right.

In total, we have moved units.