/ 
Time Limit: 2.5 sec / Memory Limit: 2048 MiB
配点 : 900 点
問題文
高橋君は全 10^9 日間からなるトーナメント形式の大会を開くことにしました。
選手は 2^N 人いて、それぞれ選手 1、\ldots、選手 2^N と呼ばれます。 選手 i は大会の l_i 日目から r_i 日目までの r_i-l_i+1 日間参加する予定です。
まず、大会の流れを述べます。1 \leq i \leq N, 1 \leq j \leq 2^{N-i} を満たす整数組 (i,j) は 2^N-1 通りありますが、それらと大会中の試合が一対一で対応します。(i,j) に対応する試合では以下に述べる 2 人の選手が対戦して勝者と敗者を決めます。
- i=1 の場合、選手 2j-1 と選手 2j
- i \geq 2 の場合、(i-1, 2j-1) に対応する試合の勝者と (i-1,2j) に対応する試合の勝者
各試合は、対戦することになる 2 人を決める為に必要な試合すべてが完了していて、かつその 2 人が大会に参加中ならばただちに完了させられます。特に、一人の選手が同日に複数の試合を行うことも可能です。
(N, 1) に対応する試合は決勝戦と呼ばれ、これを完了させるのが大会の目的です。
高橋君は決勝戦を完了させて大会を成功させるために、以下の工作を行うことにしました。
- 審判に指示を出し、各試合の勝者を都合よく決める。
- 各選手にお金を払い、参加する日程を変えてもらう。選手 i に l'_i 日目から r'_i 日目まで参加してもらう場合、|l_i-l'_i|+|r_i-r'_i| 円を支払う必要がある。ここで、l'_i, r'_i は 1\leq l'_i \leq r'_i \leq 10^9 を満たす整数である。
高橋君が選手たちに支払う必要のある金額の総和の最小値を求めてください。
制約
- 1 \leq N \leq 18
- 1 \leq l_i \leq r_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
l_1 r_1
\vdots
l_{2^N} r_{2^N}
出力
支払う必要のある金額の総和の最小値を X 円とする。X を出力せよ。
入力例 1
3 1 4 1 3 3 4 2 2 3 4 4 4 2 3 3 4
出力例 1
1
選手 4 に 1 円を払って (l'_4, r'_4)=(2,3) に変え、他の選手の日程は変えないことにします。すると、例えば以下のようにして決勝戦を完了させることができます。
- 1 日目に (1,1) に対応する試合(選手 1 対選手 2 )を行い、選手 2 を勝たせる。
- 3 日目に (1,2) に対応する試合(選手 3 対選手 4 )を行い、選手 3 を勝たせる。
- 3 日目に (2,1) に対応する試合(選手 2 対選手 3 )を行い、選手 3 を勝たせる。
- 3 日目に (1,4) に対応する試合(選手 7 対選手 8 )を行い、選手 8 を勝たせる。
- 4 日目に (1,3) に対応する試合(選手 5 対選手 6 )を行い、選手 5 を勝たせる。
- 4 日目に (2,2) に対応する試合(選手 5 対選手 8 )を行い、選手 8 を勝たせる。
- 4 日目に (3,1) に対応する試合(選手 3 対選手 8 )を行い、選手 8 を勝たせる。
一方、1 円未満の支払いで決勝戦を完了させることはできません。そのため、1 が期待される出力です。
入力例 2
1 1 1 1000000000 1000000000
出力例 2
999999999
入力例 3
4 158260522 877914575 24979445 602436426 623690081 861648772 433933447 476190629 211047202 262703497 628894325 971407775 731963982 822804784 430302156 450968417 161735902 982631932 880895728 923078537 189330739 707723857 802329211 910286918 303238506 404539679 317063340 492686568 125660016 773361868 650287940 839296263
出力例 3
1088492036
Score : 900 points
Problem Statement
Takahashi decided to hold a tournament that lasts for 10^9 days in a single-elimination format.
There are 2^N players, called player 1, \ldots, player 2^N. Player i plans to participate from day l_i to day r_i of the tournament, for a total of r_i - l_i + 1 days.
First, we describe the flow of the tournament. There are 2^N - 1 matches in total, corresponding one-to-one with the integer pairs (i, j) satisfying 1 \leq i \leq N and 1 \leq j \leq 2^{N - i}. In the match corresponding to (i, j), the following two players compete to decide the winner and the loser:
- If i = 1, players 2j - 1 and 2j
- If i \geq 2, the winners of the matches corresponding to (i - 1, 2j - 1) and (i - 1, 2j)
Each match can be completed immediately when all the matches necessary to determine the two players who will compete in it have been completed, and both players are currently participating in the tournament. In particular, a single player can participate in multiple matches on the same day.
The match corresponding to (N, 1) is called the final, and the goal of the tournament is to complete it.
To successfully complete the final, Takahashi decided to perform the following manipulations:
- Instruct the referees to fix the outcomes of the matches as desired.
- Pay the players to change their participation schedules. To make player i participate from day l'_i to day r'_i, Takahashi needs to pay |l_i - l'_i| + |r_i - r'_i| yen. Here, l'_i and r'_i are integers satisfying 1 \leq l'_i \leq r'_i \leq 10^9.
Find the minimum total amount of money Takahashi needs to pay the players.
Constraints
- 1 \leq N \leq 18
- 1 \leq l_i \leq r_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
l_1 r_1
\vdots
l_{2^N} r_{2^N}
Output
Let X be the minimum total amount of money Takahashi needs to pay. Print X.
Sample Input 1
3 1 4 1 3 3 4 2 2 3 4 4 4 2 3 3 4
Sample Output 1
1
Assume that Takahashi pays 1 yen to player 4 to change his participation schedule to (l'_4, r'_4) = (2, 3), and not change the schedules of the other players. Then, for example, the final can be completed as follows:
- On Day 1, conduct the match corresponding to (1, 1) (player 1 vs. player 2), and let player 2 win.
- On Day 3, conduct the match corresponding to (1, 2) (player 3 vs. player 4), and let player 3 win.
- On Day 3, conduct the match corresponding to (2, 1) (player 2 vs. player 3), and let player 3 win.
- On Day 3, conduct the match corresponding to (1, 4) (player 7 vs. player 8), and let player 8 win.
- On Day 4, conduct the match corresponding to (1, 3) (player 5 vs. player 6), and let player 5 win.
- On Day 4, conduct the match corresponding to (2, 2) (player 5 vs. player 8), and let player 8 win.
- On Day 4, conduct the match corresponding to (3, 1) (player 3 vs. player 8), and let player 8 win.
On the other hand, it is impossible to complete the final with less than 1 yen of payments. Therefore, the expected output is 1.
Sample Input 2
1 1 1 1000000000 1000000000
Sample Output 2
999999999
Sample Input 3
4 158260522 877914575 24979445 602436426 623690081 861648772 433933447 476190629 211047202 262703497 628894325 971407775 731963982 822804784 430302156 450968417 161735902 982631932 880895728 923078537 189330739 707723857 802329211 910286918 303238506 404539679 317063340 492686568 125660016 773361868 650287940 839296263
Sample Output 3
1088492036