Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
アイドルグループ ATC48 にて、N 人のアイドルたちに人気投票が行われ、各アイドルに a_1, a_2, \ldots, a_N の投票が集まりました。
各アイドルには得票数に応じた賞金を渡します。事前に X 円 (X は正の整数) の賞金が用意されていて、なるべくアイドル i には a_i に比例する賞金を渡したいです。しかし、A = a_1 + a_2 + \dots + a_N として X \times \frac{a_i}{A} が整数値になるとは限りません。そこで各アイドルに渡す賞金額 x_1, x_2, \ldots, x_N を以下の条件を満たす 0 以上の整数値となるように決めることにしました:
- x_1 + x_2 + \ldots + x_N = X
- |\frac{x_1}{a_1} - \frac{X}{A}| + |\frac{x_2}{a_2} - \frac{X}{A}| + \ldots + |\frac{x_N}{a_N} - \frac{X}{A}| が最小値をとる。
各アイドルの賞金額 x_1, x_2, \ldots, x_N を出力するプログラムを作ってください。複数通り考えられる場合には、(x_1, x_2, \ldots, x_N) の辞書順が最小のものを出力してください。
制約
- 1 \le N \le 10^5
- 1 \le X \le 10^9
- 1 \le a_i \le 100
- 与えられる入力はすべて整数です。
入力
入力は以下の形式で標準入力から与えられます。
N X a_1 a_2 \ldots a_N
出力
各アイドルの受け取る賞金額 x_1, x_2, \ldots, x_N をこの順に一行ずつ出力してください。
入力例 1
4 100 3 4 5 8
出力例 1
15 20 25 40
この場合はちょうど比例配分することができます。
入力例 2
2 100 3 4
出力例 2
43 57
このとき |\frac{43}{3} - \frac{100}{7}| + |\frac{57}{4} - \frac{100}{7}| = 0.083333… となります。
入力例 3
6 1000 7 6 1 3 4 1
出力例 3
318 273 45 136 182 46
複数通り考えられる場合は、辞書順最小のものを出力します。