Solve ABC146-C in Python

Introduction

Solve the problem of binary search.

Buy an Integer

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)

Summary

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

Solve ABC146-C in Python
Solve ABC098-C in Python
Solve ABC168D in Python
Solve ABC167-D in Python
Solve ABC159-D in Python
Solve ABC169 in Python
Solve ABC160-E in Python
Solve ABC176 E in Python
Solve Wooldridge exercises in Python
Solve ABC175 D in Python
Solve optimization problems in Python
Solve Atcoder ABC169 A-D in Python
Solve ABC036 A ~ C in Python
Solve ABC037 A ~ C in Python
Solve ordinary differential equations in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Solve ABC175 A, B, C in Python
ABC 157 D --Solve Friend Suggestions in Python!
I wanted to solve ABC159 in Python