Implement a circular expression binary search in Python. There is a comparison with a simple full search.

For example, this [problem] of AtCoder (https://atcoder.jp/contests/abc146/tasks/abc146_c?lang=ja) (C of abc146)

When I try to solve it with a linear search, the search range is $ 1 ≤ A ≤ 10 ^ {9} $, so the calculation does not finish in time. (* TLE is about $ 10 ^ {8} $ to $ 10 ^ {9} $.)

Let's implement it as a trial.

A,B,X = map(int,input().split())

max_int = 0
for i in range(1,10**9+1):
    if (A * i) + ( B * (len(str(i))) ) <= X:
        max_int = i
    else:
        break

print(max_int)

It is an implementation that honestly investigates from scratch, but when you submit this, as expected, most of them will be TLE. Looking at this algorithm, it checks whether the condition is satisfied by increasing it by 1 in order from 1.

This is the same as searching for a sorted array of $ 1,2,3,4,5,6 ,,,, 10 ^ {9} $. Speaking of algorithms that can be used when sorted like this ,. Yes, it's a binary search.

Let's implement it in the same way as described in the algorithm textbook.

A,B,X = map(int,input().split())

#Define a range of integers you want to search
left = 1
right = 10 ** 9

#Conditions to be met
def validate(arg):
    if (A * arg) + ( B * (len(str(arg))) ) <= X:
        return True

#Binary search to find the maximum integer that satisfies the condition
max_int = 0
while left <= right:
    mid = (left+right) // 2
    if validate(mid):
        max_int = mid
        left = mid + 1
    else:
        right = mid -1

print(max_int)

In a normal binary search, the While statement is exited when a value that satisfies the condition is found, but this problem is to find the maximum integer that satisfies the condition, so continue as it is. However, the point is to update max_int only if the conditions are met. Using mid in this code for the answer is buggy.

This is not a problem, but as pointed out in the formula, it is easy to get a bug at the final boundary judgment if you are not careful about mid + 1 and mid -1. Also, the condition judgment of While is a point where it is easy to make a mistake as to whether it is <or <=.

So, if you rewrite it with reference to the Meguru formula, it will be like this.

• If you refer to the Meguru formula, you can find the maximum left that satisfies the condition until right-left> 1. For more information here

※※ Meguru-shiki Honke here

A,B,X = map(int,input().split())

#Define a range of integers you want to search
left = 0
right = 10 ** 9 + 1

#Conditions to be met
def validate(arg):
    if (A * arg) + ( B * (len(str(arg))) ) <= X:
        return True

#Binary search to find the maximum integer that satisfies the condition
max_int = 0
while abs(right - left) > 1:
    mid = (left+right) // 2
    if validate(mid):
        max_int = mid
        left = mid
    else:
        right = mid

print(max_int)

In the case of the Meguru formula, the point is to increase it by one from the upper and lower limits of the range you want to search. In the case of this code, left = 0 right = 10 ** 9 + 1.

It doesn't look like a big change, but you don't have to worry about the disappearance of +1 -1 and> = or>.

When the difference between abs (right --left) becomes 1, the process ends.