[Algospot] 이진탐색 / RATIO / Python 파이썬

[Algospot] 이진탐색 / RATIO / Python 파이썬

 

https://www.algospot.com/judge/problem/read/RATIO#

algospot.com :: RATIO

 

 

풀이

주어진 승률에서, 승률을 1% 올리기위한 연승 횟수를 구하는 문제이다.

 

먼저, 최대 횟수 연승 후에도 승률 1% 가 오르지 않는 경우를 제외하였다.

그리고 최소 연승 횟수가 최대 연승 횟수와 같아질 때 까지 이진탐색을 시행하였다.

 

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    Z = int(M * 100 / N)
    Max = 2000000000

    if int((M+Max) * 100 / (N+Max)) == Z:
        print(-1)
    else:
        hi = Max
        lo = 0

        while lo + 1 < hi:
            half = (hi+lo) // 2
            Z_ = int((M+half) * 100 / (N+half))
            if Z == Z_:
                lo = half
            else:
                hi = half
        print(hi)