SamCoding Round 10 (Div. 4) B - Bookworm
- サイト
- SamCoding
- コンテスト
- SamCoding Round 10 (Div. 4)
- 問題
- B - Bookworm(常設版)
Jasur は ページの本を読みます。 日目は ページ読み、その後は毎日、前の日より ページ多く読みます( 日目は ページ、 日目は ページ、…)。残りのページが予定より少ない日は、残りを読んで読み終えます。何日目に読み終えるかを求める問題です(、)。
日目までに読む予定のページ数の合計は
です。 となる最小の が答えです。
は について単調増加なので、二分探索で求められます。 より なので、答えは 以下です。探索の上限は にしています。
Python
n, a, k = map(int, input().split())ok = 10**15ng = 0while ok > ng + 1: mid = (ok + ng) // 2 if n <= mid * a + mid * (mid - 1) // 2 * k: ok = mid else: ng = midprint(ok)ok は を満たす 、ng は満たさない を保ちながら、区間を半分ずつ狭めています。