Solve the problem of binary search.
Trying all the integers sold will give you a TLE. Therefore, we have to reduce the amount of calculation well, so we use binary search. Binary search is a method of searching for the desired solution by narrowing the range from both ends. Detailed explanation. The computational complexity of the binary search is $ O (log N) $, so it is in time.
a,b,x = map(int,input().split())
max_n = 10**9+1 #Maximum value of n is 10**Because it is 9+1
min_n = 0
while max_n - min_n > 1:
mid_n = (max_n+min_n)//2
if x < a*(mid_n)+b*len(str(mid_n)):
max_n = mid_n
else:
min_n = mid_n
print(min_n)
If you can use binary search well, you can greatly reduce the amount of calculation, so I want to master it. see you.
Recommended Posts