Addition Chains
题号:NC50244
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

输入描述:

第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为N个用空格隔开的正整数,表示N根小木棍的长度。

输出描述:

输出仅一行,表示要求的原始木棍的最小可能长度。
示例1

输入

复制
5
7
12
15
77
0

输出

复制
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

备注: