No.68 よくある棒を切る問題 (2)

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

問題一覧 > 通常問題

No.68 よくある棒を切る問題 (2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が$10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 103
作問者 :

LayCurse

13 ProblemId : 146 / 出題時の順位表 / 自分の提出

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

問題文

ユウキさんは $N$ 本の棒を持っていて、$i$ 番目の棒の長さは $L_i$ です。
棒は（長さを分割する方向に）自由に切ることができますが、繋げることはできません。
ユウキさんは同じ長さの棒を作りたいのですが、何本であればどのぐらいの長さにできるかが気になっています。
同じ長さの棒を $K_1, K_2,\ldots,K_Q$ 本作るとしたら、その時の棒の長さの最大値をそれぞれ求めるプログラムを書いて下さい。

入力

\(N\)
\(L_1\ L_2\ \cdots\ L_N\)
\(Q\)
\(K_1\ K_2\ \cdots\ K_Q \)

$1 \leq N \leq 100000 = 10^5$
$1 \leq L_i \leq 1000000000 = 10^9$
$1 \leq Q \leq 100000 = 10^5$
$1 \leq K_i \leq 500000 = 5 \times 10^5$

出力

$i$ 行目には $K_i$ 本の同じ長さの棒を作る際の、作れる長さの最大値を出力せよ。
絶対誤差、または、相対誤差が $10^{-9}$ 以下であれば正答とみなされる。

サンプル

サンプル1

入力

出力

10.00
6.666666666666667

長さ $20$ の棒をちょうど $2$ 等分することで長さ $10$ の棒が $3$ 本できます。
また、長さ $20$ の棒を $3$ 等分し、長さ $10$ の棒から $20/3$ の長さだけ残して切って、残りを捨てることで長さ $20/3$ の棒が $4$ 本できます。

サンプル2

入力

5
99 88 77 66 55
5
1 10 100 1000 100000

出力

99
33
3.807692307692307
0.384279475982533
0.003849923001540

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

yukicoder