コンテンツにスキップ

SamCoding Round 10 (Div. 4) B - Bookworm

サイト
SamCoding
コンテスト
SamCoding Round 10 (Div. 4)
問題
B - Bookworm(常設版)

Jasur は nn ページの本を読みます。11 日目は aa ページ読み、その後は毎日、前の日より kk ページ多く読みます(22 日目は a+ka + k ページ、33 日目は a+2ka + 2k ページ、…)。残りのページが予定より少ない日は、残りを読んで読み終えます。何日目に読み終えるかを求める問題です(1≤n,a≤10121 \le n, a \le 10^{12}、0≤k≤10120 \le k \le 10^{12})。

mm 日目までに読む予定のページ数の合計は

f(m)=ma+m(m−1)2kf(m) = ma + \frac{m(m - 1)}{2} k

です。f(m)≥nf(m) \ge n となる最小の mm が答えです。

ff は mm について単調増加なので、二分探索で求められます。a≥1a \ge 1 より f(n)≥nf(n) \ge n なので、答えは n≤1012n \le 10^{12} 以下です。探索の上限は 101510^{15} にしています。

Python
n, a, k = map(int, input().split())
ok = 10**15
ng = 0
while ok > ng + 1:
mid = (ok + ng) // 2
if n <= mid * a + mid * (mid - 1) // 2 * k:
ok = mid
else:
ng = mid
print(ok)

ok は f(m)≥nf(m) \ge n を満たす mm、ng は満たさない mm を保ちながら、区間を半分ずつ狭めています。