Informatica Online Judge

  세그먼트 [1191 / 04A7]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 24   Total Tried : 30


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[CCC 2005 Day1]

Background

n(1<= n <=20000) 개의 층, n개의 구역으로 나뉘어있는 건물에서 가장 빠른 경로로 내려와야 하는데, 각 층에는 반드시 지나가야하는 구역(세그먼트)의 좌표 L(k), R(k) 가 주어진다.(1<= L(k) <= R(k) <=n).

건물의 가장 꼭대기 가장 왼쪽 위치인 (1,1)에서 건물의 가장 바닥 층의 가장 오른쪽인 (n, n)까지, 각 층의 세그먼트들을 반드시 지나며 내려오는 이동하는 최단거리를 찾아야 한다.

k 층에서

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

좌표들은 반드시 지나가야 하고, 한 층을 아래로 내려가면 왼쪽, 오른쪽, 아래쪽으로만 움직일 수 있으며, n번째 줄의 세그먼트를 모두 지나간 후 (n,n) 위치로 이동해야 한다.

(1,1)에서 각 층의 모든 세그먼트들을 지나 (n,n) 까지 이동하는 최단거리를 출력하시오. 단, 한 층 내려가면 한 구역 이동한 만큼 이동 거리가 늘어난다.

Input

첫 줄에는 건물의 높이(구역) n이 주어진다.
이 후의 n개의 줄에는 각 층의 세그먼트 좌표 L(k) R(k)가 공백을 두고 입력된다.

Output

(1,1)에서 각 층의 모든 세그먼트들을 지나 (n,n) 까지 이동하는 최단거리를 출력하시오.

IO Example

입력
6
2 6
3 4
1 3
1 2
3 6
4 5

출력
24

예시 설명

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


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]