Algorithm PS/Algospot
[Algospot] 이진탐색 / RATIO / Python 파이썬
migrationArc
2021. 9. 22. 14:48
https://www.algospot.com/judge/problem/read/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)