F - Vinculum Editorial /

Time Limit: 2 sec / Memory Limit: 63 MB

配点

満点
100
部分点1
20
部分点2
40

問題文

分数の真ん中の線分を括線(Vinculum)という。分数の計算時、短い括線から順に計算するという暗黙のルールがある。

N個の非0実数列\{a_N\}が与えられる。これを上から下に一列にならべ、間に1~N-1の相異なる長さの括線を引くことで、分数を表しかつその計算順序も表現できる。

たとえば次の図では1.02.0の間に長さ3の括線、2.03.0の間に長さ1の括線、3.04.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_ia_ia_{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

Writer: uwi

Source Name

Autumn Fest