Tarzan的文章

Tarzan的文章

Problem Description

有一天 Tarzan 写了一篇文章,我们发现这文章当中一共出现了 n 个汉字,其中第 i 个汉
字出现了 ai 次,因为 Tarzan 不希望文章被别人偷看,他要给这 n 个字分别用一个特殊的字
符串表示,其中每一个字符串由两类字符组构成,一类是 a,另一类是 ha,例如 ahaha 就是
由 a、 ha 和 ha 构成的,我们希望帮助 Tarzan 给每个汉字一个独一无二的字符串,其中不能
存在两个字符串一个是另一个的前缀。我们同时希望文章尽量短,太长会把女神惹烦,文章
长度就是每一个汉字出现次数乘以对应字符串的长度之和,请输出最短的文章长度。

Input format

第一行一个整数 n 表示汉字数量。
第二行 n 个整数,分别表示每个汉字的出现次数。

Output format

一行一个整数表示最短的文章长度。

Examples

input 1

3 9

output 1

2 1 1

input 2

4 27

output 2

1 2 3 4

Constrains and Notes

对于 15% 的数据满足: n ≤ 15
对于 40% 的数据满足: n ≤ 100
对于 70% 的数据满足: n ≤ 400
对于 100% 的数据满足: 3 ≤ n ≤ 750; 1 ≤ ai ≤ 100000,数据保证存在一定的阶梯性
时限:1s,空间限制:128MB

信息

ID
1394
难度
9
分类
树结构 | 动态规划 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
被复制
2
上传者