← 返回题目列表

Codeforces · 178/A2

A2. 教育游戏

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

ABBYY 的智能海狸开始开发一款新的儿童教育游戏。游戏规则相当简单,如下所述。

比赛场地是 n 个非负整数 ai 的序列,编号从 1 到 n。游戏的目标是对于某个固定的 k (k < n),使数字 a1、a2、...、ak(即序列的某个前缀)等于 0,并且这应该以尽可能少的步数完成。

一步是选择一个整数 i (1 ≤ i ≤ n) 使得 ai > 0 和一个整数 t (t ≥ 0) 使得 i + 2t ≤ n。 i 和 t 的值选定后,ai 的值减 1,ai + 2t 的值加 1。例如,令 n = 4,a = (1, 0, 1, 2),则可以走 i = 3,t = 0,得到 a = (1, 0, 0, 3),或者走 i = 1,t = 1,得到 a = (0, 0, 2, 2)(唯一可能的其他移动是 i = 1, t = 0)。

给定 n 和初始序列 ai。任务是计算对于每个可能的 k (1 ≤ k < n),使原始序列的前 k 个元素等于 0 所需的最小移动次数。

输入

第一个输入行包含单个整数 n。第二行包含 n 个整数 ai (0 ≤ ai ≤ 104),用单个空格分隔。

获得 20 点的输入限制为:

- 1 ≤ n ≤ 300

获得 50 点的输入限制为:

- 1 ≤ n ≤ 2000

获得 100 点的输入限制为:

- 1 ≤ n ≤ 105

输出

精确打印 n - 1 行:第 k 个输出行必须包含使原始序列 ai 的前 k 个元素等于 0 所需的最小移动次数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

4
1 0 1 2

输出 #1

1
1
3

输入 #2

8
1 2 3 4 5 6 7 8

输出 #2

1
3
6
10
16
24
40