問題一覧 > 通常問題

No.67 よくある棒を切る問題 (1)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 309
作問者 : LayCurseLayCurse
4 ProblemId : 145 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:51

問題文

ユキさんは \(N\) 本の棒を持っていて、\(i\) 番目の棒の長さは \(L_i\) です。
棒は(長さを分割する方向に)自由に切ることができますが、繋げることはできません。
ユキさんは同じ長さの \(K\) 本の棒を作りたいのです。
作れる \(K\) 本の棒の長さの最大値を求めるプログラムを書いて下さい。

入力

\(N\)
\(L_1\ L_2\ \cdots\ L_N\)
\(K\)

入力は全て整数で与えられる。
\(1 \leq N \leq 200000 = 2 \times 10^5\)
\(1 \leq L_i \leq 1000000000 = 10^9\)
\(1 \leq K \leq 10000000000 = 10^{10}\)

出力

作れる長さの最大値を \(1\) 行で出力せよ。
絶対誤差、または、相対誤差が $10^{-9}$ 以下であれば正答とみなされる。
最後に改行すること。

サンプル

サンプル1
入力
2
10 20
3
出力
10.00

長さ \(20\) の棒をちょうど \(2\) 等分することで長さ \(10\) の棒が \(3\) 本できます。

サンプル2
入力
2
10 20
4
出力
6.666666666666667

長さ \(20\) の棒を \(3\) 等分し、長さ \(10\) の棒から \(20/3\) の長さだけ残して切って、残りを捨てることで長さ \(20/3\) の棒が \(4\) 本できます。

サンプル3
入力
5
99 88 77 66 55
1
出力
99
サンプル4
入力
5
99 88 77 66 55
10
出力
33
サンプル5
入力
5
99 88 77 66 55
100000
出力
0.003849923001540

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。