← 返回题目列表

AtCoder · autumn_fest_06

F. 文库鲁姆

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

配点

満点
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_N
N是数列的长度项数,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

作者: 西印度群岛大学