配点
- 満点
- 100
- 部分点1
- 20
- 部分点2
- 40
問題文
分数中间的线段称为括线(Vinculum)。在分数计算时,有一个隐含规则是从短括线开始依次计算。
给出 N 个非0実数列\{a_N\}。将它们从上到下排列成一列,在之间1~N-1画长度不同的括线,从而表示分数及其计算顺序。
例如,在下图中1.0和2.0之间的长度3的括线、2.0和3.0之间的长度1的括线、3.0和4.0之间的长度2的括线通过画出的分数来计算,结果是6.0。这种划线方式,在数列[ 1.0, 2.0, 3.0, 4.0 ]的括线划法中实现了最大值。
図1
当从短的括线依次计算时,求出最终结果最大化的括线长度序列。
入力形式
输入以以下格式给出。
N\\ a_1\ a_2\ ...\ a_NN是数列的长度项数,a_i表示从上数第 i 个放置的数字。
出力形式
以以下格式输出。
L_1\\
L_2\\
...\\
L_{N-1}
N-1个1~N-1由不同的整数组成,以换行分隔输出。L_i是a_i和a_{i+1}表示两者之间划线的长度。
当解有多个时,可以输出其中任意一个。
制約
- 2 ≤ N ≤ 10000
- a_i是非0的实数,整数部分恰好有1位,小数部分恰好有1位数。也就是说-9.9,-9.8,...-1.1,-1.0,-0.9,...-0.1,0.1,...,0.9,1.0,1.1,...,9.9中的任意一个。
以上记为基本否定。
对于这个问题的判定,20 点的测试用例组已被设定。包含在这个组中的测试用例,除了满足基本否定外,还需满足以下否定。
- 2 ≤ N ≤ 9
对于这个问题的判定,40 点的测试用例组已被设定。包含在这个组中的测试用例,除了满足基本否定外,还需满足以下否定。
- 2 ≤ N ≤ 50
入力例 1
4 1.0 2.0 3.0 4.0
出力例 1
3 1 2
是问题文中的例子。
入力例 2
4 0.1 0.2 0.3 0.4
出力例 2
1 2 3
入力例 3
4 9.9 0.1 -9.9 -0.1
出力例 3
3 2 1
作者: