Starting today, I will solve atcoder with python.
https://atcoder.jp/contests/abc146/tasks/abc146_c This problem is the most typical problem of binary search. Binary search and theory are simple, but if you implement it, you may or may not WA at the boundary. However, if I narrow down to the last two, I don't want to be muddy to try and answer both ww
This time, is a binary search that fills in from the left side (a type of binary search that searches for the number that does not exceed a certain number)
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
The point of this time to prevent bugs at the boundary is
if p > x:
r = m
else:
l = m
It is the part of. Why is this the point! ??
It is l + (r --l) // 2 Look here. Rewriting, (l + r) // 2 That's the part. (Do not exceed the number of digits. I often hear the theory that PYTHON is unnecessary)
This value is 10.5 or 1000.5 when l + r divided by // is odd, and when it is float, a fraction appears and it is rounded down. In other words, m depends on feeling left </ font>
Some people may get angry when they read this and say, "It's too sloppy! Don't be silly!"
I want to say loudly to those people.
~~ I'm sorry ~~
I can't go over it, so I think it's okay to make it feel like it's coming from the left It's about the idea.
See you soon
Recommended Posts