太巻きを分けよう (おなかペコペコ)
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ L [cm] の太巻きがあり、これを n 人で分けようとしています。太巻きにはあらかじめ k 個の切れ目が入っており、i 個目の切れ目は左端から A_i [cm] のところに入っています。あなたは、切れ目を n-1 個選んでそこで切ることにより、太巻きを n 分割しようとしています。n 人はみなお腹がすいているので、なるべくたくさん食べたいと思っています。切れ目の選び方を工夫したとき、最も短い太巻きの長さを最大でいくつにできるかを答えてください。
- 入力される値
-
L n k
A_1 A_2 ... A_k
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
切れ目を適切に n-1 個選んで太巻きを n 分割した結果、最も短い太巻きの長さを最大でいくつにできるかを出力してください。なお、本問の制約において、答えは必ず整数になります。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 10 ≦ L ≦ 10^9
・ 1 ≦ n ≦ 100,000
・ n-1 ≦ k ≦ 200,000
・ 0 < A_1 < A_2 < ... < A_k < L
- 入力例1
-
23 5 7
2 6 9 10 12 15 19
- 出力例1
-
4
