← 返回题目列表

AtCoder · agc069_a

A. 日程优化

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

高桥决定举办一场持续 10^9 天,采用单淘汰赛制。
有 2^N 玩家,称为玩家 1, \ldots,玩家 2^N。玩家 i 计划从当天开始参加 l_i 到今天 比赛的 r_i ,总共 r_i - l_i + 1 天。

首先,我们描述一下锦标赛的流程。有 2^N - 1 总共匹配,与整数对一一对应 (i, j) 满意 1 \leq i \leq N 和 1 \leq j \leq 2^{N - i}。在对应的比赛中 (i, j),以下两名选手进行比赛,决出胜负:

  • If i = 1,玩家 2j - 1 和 2j
  • If i \geq 2, 对应比赛的获胜者 (i - 1, 2j - 1) 和 (i - 1, 2j)

当确定参加比赛的两名选手所需的所有比赛都已完成且两名选手当前都在参加比赛时,每场比赛可以立即完成。特别是,单个玩家可以在同一天参加多场比赛。
对应的匹配 (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

假设高桥支付 1 日元给玩家 4 将其参与日程更改为 (l'_4, r'_4) = (2, 3),并且不改变其他玩家的赛程。那么例如最终可以完成如下:

  1. 当天 1,进行对应的匹配 (1, 1) (玩家 1 对阵玩家 2),并让玩家 2 赢了。
  2. 当天 3,进行对应的匹配 (1, 2) (玩家 3 对阵玩家 4),并让玩家 3 赢了。
  3. 当天 3,进行对应的匹配 (2, 1) (玩家 2 对阵玩家 3),并让玩家 3 赢了。
  4. 当天 3,进行对应的匹配 (1, 4) (玩家 7 对阵玩家 8),并让玩家 8 赢了。
  5. 当天 4,进行对应的匹配 (1, 3) (玩家 5 对阵玩家 6),并让玩家 5 赢了。
  6. 当天 4,进行对应的匹配 (2, 2) (玩家 5 对阵玩家 8),并让玩家 8 赢了。
  7. 当天 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