Pythonでアルゴリズム（ABC 146 C 二分探索

今日からatcoderをpythonで解いていきます。

https://atcoder.jp/contests/abc146/tasks/abc146_c
　
この問題は二分探索の最も典型的な問題です。
二分探索、理論はシンプルですが実装すると境界でWAしたりしなかったりしてしまいますよね。
かといって最後の２つに絞れたら２つとも試してみて答える、なんて泥臭いこともしたくないですｗｗ

今回は、左側から詰めていく二分探索（ある数を超えないぎりぎりの数を探すタイプの二分探索です）

l = 0
r = 1000000001

a, b, x = tuple(map(int, input().split(" ")))
while l < r - 1:
  m = l + (r - l) // 2
  p = m * a + b * len(str(m))
  if p > x:
    r = m
  else:
    l = m

print(l)
#l = left, m = middle, r = right

境界でバグらせないための今回のポイントは

  if p > x:
    r = m
  else:
    l = m

の部分です。
なんでここがポイントなの！？

それは、l + (r - l) // 2
ここを見てください。
書き換えると、(l + r) // 2
の部分ですね。（桁数がオーバーしないように。PYTHONなら不要という説をよく聞きます）

この値って、//で割られているのl+rが奇数のときは10.5とか1000.5とか、floatだと端数が出てきててこれを切り捨てています。
つまり、mはキモチ左によっている

これを読んで「いい加減すぎる！ふざけるな！！」と怒る人がいるかもしれません。

そういう人たちには声を大にして言いたい。

すみませんでした

超えちゃいけないから恐る恐る左から寄ってくる感じにしたらいいんじゃないかな
くらいの発想です。

ではでは