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

問題提出提出一覧質問統計解説

問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が

10^{- 9}

以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 317
作問者 :

LayCurse

4 ProblemId : 145 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2015-11-14 17:46:51

問題文

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

入力

 $N$ 
 $L_{1} L_{2} \dots 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

出力

サンプル4

入力

5
99 88 77 66 55
10

出力

サンプル5

入力

5
99 88 77 66 55
100000

出力

0.003849923001540

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

yukicoder