传统题 1000ms 256MiB

Memory Limit Exceeded

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

1024是程序员节日,程序员就应该加班、板砖做一个合格的码农!!!

Joanh_LanJoanh\_LanBOSSBOSS 为了逃避给员工发礼物,于是就抛出了一个奇怪的要求(谁让TaTa是产品经理),如果哪个员工可以帮TaTa实现,TaTa将给他一笔不菲的奖金。

Joanh_LanJoanh\_Lan想获得这一笔钱,但他不会解决这个问题,于是他来请求你来帮他解决这个难题,如果Joanh_LanJoanh\_Lan可以获得这一笔奖金,那么他的生活与命运将得到难以想象的改变(这对他是一个可遇不可求的机会,请你认真帮他解决,他将对你感激不尽!!!)


问题描述

有一个奇特的网红公园有2n+112^{n + 1} - 1 条道路连接,也就是说公园是一个深度为nn的满二叉树。

类似这个:

满二叉树

注:上图深度为:3

你不必纠结什么是深度,什么是满二叉树。

如果你知道,那对你做题会有帮助

如果你不知道,请接下来认真读题,Joanh_LanJoanh\_Lan满眼期待的看着你。

你从1号位置出发,到2n2^n2n+12^n + 1 或 ... 或 2n+112^{n + 1} - 1,为了更好的理解,如果按照上图,就是

11889910101111 或 ... 或 14141515

也就是说:你要从起点(最上面) 走到 终点(最下面)

因此你一定会沿着 nn 条道路从最上面走到最下面(如果你严格向下走的话)

因为是网红公园,不同地点都有不同的特色。每个地点都有一个 游客喜爱值,喜爱值越大该地点越受游客的喜爱!

地点标号严格按照上图标号模式

因为你严格从最上面走到最下面可以明确有 2n2^n 条路径走法,我们约定: F(X)=X路径经过的地方的游客喜爱值F(X) = \sum X路径经过的地方的游客喜爱值

网红公园的老板为了防止不同线路的体验不同,决定出资去提升某地方的游客喜爱值(可以选多个地方进行提升游客喜爱值)

提升1点游客喜爱值需要花费1单位的代价,老板想花费最小代价去完成他的想法:

F(X1)=F(X2)=...=F(XK)=...F(X2n)F(X_1) = F(X_2) = ... = F(X_K) = ... F(X_{2^n} )

输入

第一行包含一个整数 n (1n10)n\ (1 \le n \le 10) 从入口(最上面)到 任何出口(最下面)的路径上的道路上数。

下面包含 2n+122^{n + 1} - 2 个数字 a2,a3...a2n+11a_2,a_3 ... a_{2^{n + 1}- 1} 网红公园第 ii 个地方的游客喜爱度。ai是一个正整数,ai100a_i 是一个正整数,a_i \le 100

输出

打印一个整数 —— 最小代价

样例

input

2
1 2 3 4 5 6

output

5

注意:样例的图片:绿色表示初试游客喜爱度,粉色表示通过花费代价增加的游客喜爱度

样例解释

2022ACM新生积分赛 Round #3

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2022-10-29 13:00
结束于
2022-10-29 18:00
持续时间
5 小时
主持人
参赛人数
70