[1072] 게임

문제 출처 : https://www.acmicpc.net/problem/1072

분류 : 수학, 이분탐색

백준 1072 게임

parametric search

---

구현 포인트

1) 처음부터 99퍼나 100퍼라면 절대 증가할 수 없다.

2) 이분 탐색으로 시간을 줄이자.

문제는 아래와 같다.

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 

누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 

그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 

자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

게임 횟수 : X
이긴 게임 : Y (Z %)
Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 몇 판해야 Z가 변하는지 구하는 프로그램을 작성하시오. 

만약 Z가 절대 변하지 않는다면 -1을 출력한다.

입력

각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다.

 

우선 여기서 고려해야 할 점은 네 가지 정도가 있다.

1) z를 구하는 함수는 단조 증가하게 된다.

   무조건 앞으로의 게임에서는 승리를 하므로 함수가 증가하게 된다.

2) z를 구하는 과정에서 100을 곱하므로 long long 자료형 사용이 필요하다.

3) 일일히 z를 구하면서 모든 경우를 보기에는 시간이 오래걸린다.

4) 99퍼나 100퍼가 나오면 증가할 수가 없다.

1)번과 3)을 고려할 때 우리는 parametric search가 가능하다는 사실을 알게 된다.

x를 증가시킬 때 마다 z의 값은 단조 증가하기 때문이다. (실제 실수형 계산이든, C style의 내림 계산이든)

그리고 x의 증가 범위는 2x를 넘을 수 없다는 사실 또한 수학적으로 알 수 있다.

따라서 x부터 2x의 범위 사이에서 z보다 커지게 되는 값을 이분적으로 찾으면 된다.

코드는 아래와 같다.

#include<cstdio>
typedef long long ll;
ll x, y, z;
int f(ll i) {
    return (y + i-x) * 100 / (i);
}
int main() {
    while (2 == scanf("%lld %lld", &x, &y)) {
        z = y * 100 / x;
        if (z == 100 || z == 99) printf("-1\n");
        else {
            ll low = x, high = 2 * x;
            while (low <= high) {
                ll mid = (low + high) / 2;
                if (f(mid) <= z) {
                    low = mid + 1;
                }
                else {
                    high = mid - 1;
                }
            }
            printf("%lld\n",low-x);
        }
    }
}