플레이어의 게임 횟수 N와 승리 횟수 M

승률은 정수이다.

N과 N이 주어질 때, 승률이 1% 올라가기 위해 해야 할 최소 게임 수를 출력하라.

만약 20억 게임 내에 올릴 수 없다면 -1 출력

제한 시간 10초

만약 20억 번에 대해 다 계산하면 시간 넘김

단순 부등식 계산

사실 이 문제는 식이 복잡하지 않아서 부등식 계산이 가능하다.

이분법

// 최대 게임 수
long long L = 2000000000;
// b게임 중 a게임 승리했을 때의 승률
int ratio(long long b, long long a)
{
	return (a * 100) / b;
}
// 최소 몇 연승해야 승률이 올라갈까?
int neededGames(long long games, long long won)
{
	// 불가능한 경우를 미리 걸러낸다.
	if (ratio(games, won) == ratio(games + L, won + L))
		return -1;
	long long lo = 0, hi = L;
	// 반복문 불변식:
	// 1. lo 게임 이기면 승률은 변하지 않는다.
	// 2. hi 게임 이기면 승률은 변한다.
	while (lo + 1 < hi)
	{
		long long mid = (lo + hi) / 2;
		if (ratio(games, won) == ratio(games + mid, won + mid))
			lo = mid;
		else
			hi = mid;
	}
	return hi;
}