[백준][C++] 1072: 게임

문제 링크: https://www.acmicpc.net/problem/1072

 

식을 세워서 O(1)로 해결할 수 있습니다.

일단 승률이 99% 이상이면 승률을 올리는 것이 불가능합니다. 승률이 100%이면 당연히 101%로 올리는 것은 불가능하고요, 99%인 경우도 100%로 올릴 수 없습니다.

그럼 승률이 98% 이하일 때 몇 판을 이겨야 승률이 1% 올라갈까요? 적당히 식을 세워서 알 수 있습니다.

 

\[Z=\left\lfloor \frac{Y}{X} * 100 \right\rfloor\]

Z는 현재 승률이고 위 식으로 계산할 수 있습니다.

n판을 더 이겼을 때 승률이 1% 올라간다고 했을 때 식을 세워봅시다. 이때 승률을 Z+ 라고 하겠습니다.

 

\begin{align}
\frac{Y+N}{X+N} &= \frac{Z^+}{100} \\
100Y+100N &= Z^+(X+N) \\
(100-Z^+)N &= Z^+*X-100Y\\
\therefore N &= \left\lceil \frac{Z^+*X-100Y}{100-Z^+} \right\rceil
\end{align}

참쉽죠?

이분탐색으로도 아마 풀 수 있지 않을까 생각합니다.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	ll x, y;
	cin >> x >> y;

	if ((y*100) / x >= 99)
		cout << -1 << '\n';
	else {
		ll z = (y * 100) / x;
		++z;

		ll nn = z*x - 100*y;
		if (nn % (100 - z) == 0)
			cout << nn / (100-z) << '\n';
		else
			cout << (nn / (100-z)) + 1 << '\n';
	}


	return 0;
}