← 返回题目列表

Codeforces · 526/B

B. Om Nom 和黑暗公园

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

Om Nom 是游戏“割绳子”的主角。他是一个聪明的小怪物,喜欢拜访住在公园另一边的朋友。然而,黑暗的古老公园甚至会吓到像 Om Nom 这样无所畏惧的人,所以他请求你帮助他。

公园由 2n + 1 - 1 个由道路连接的正方形组成,因此公园的方案是深度为 n 的满二叉树。更正式地说,公园的入口位于广场 1。公园的出口位于广场 2n、2n + 1、...、2n + 1 - 1,这些出口直接通向 Om Nom 朋友的房子。从每个方格 i (2 ≤ i < 2n + 1) 都有一条通往方格 $$\frac{i}{2}$$ 的路。因此,从公园入口到每个出口,可以恰好沿着n条路行走。

Om Nom 喜欢在去朋友家的路上数灯。 Om Nom 害怕公园里的蜘蛛,所以他不喜欢沿着光线不足的道路行走。他想要的是,通往他任何一个朋友的路上应该有相同数量的灯。这会让他感到安全。

他要求你帮他安装额外的灯。确定需要在公园道路上额外安装多少盏灯,以便从公园入口到任何出口的路径包含相同数量的路灯。您可以向每条道路添加任意数量的路灯。

输入

第一行包含整数 n (1 ≤ n ≤ 10) — 从入口到任意出口的路径上的道路数量。

下一行包含 2n + 1 - 2 个数字 a2, a3, ... a2n + 1 - 1 — 公园每条道路上路灯的初始数量。这里 ai 是方块 i 和 $$\frac{i}{2}$$ 之间道路上的路灯数量。所有数字ai都是正整数,不超过100。

输出

打印出我们应该在公园道路上添加的最少路灯数量,以使 Om Nom 感到安全。

示例

输入 #1

2
1 2 3 4 5 6

输出 #1

5

注意

样本测试图片。绿色表示额外的路灯。