Spider Solitaire를 즐기는 형택이가 현재 게임 승률에서 몇 판 더 했을 때 자신의 승률이 바뀌는지 알아보자.
처음에는 예외를 잡는 부분이 생각보다 어려웠다. 최대 시도를 10억번을 기준으로 이분 탐색을 진행해서 10억이 넘어가면 -1로 출력하는줄 알았으나.
질문 게시판을 보고 그냥 승률이 99%가 넘는다면 예외 조건은 존재하지 않는다.
0 ~ 10억 + a로 해서 이분탐색을 진행 하는게 그저인 문제. 기준은 초기 z값을 기준으로 현재 게임 수를 더한 임시 tempZ가 작거나 같으면 최소 범위를, 반대인 경우 최대 범위를 축소 시키면 된다.
문제에는 명시가 안되어 있지만. TCC가 1개로 한정 된게 아니라. 여러 개 존재한다. EOF를 통해 계속 입력 받도록 해야한다.
#include <iostream>
using namespace std;
const int MAX = 1500000000;
int main()
{
int res = -1;
long long x, y;
int z;
while (cin >> x >> y)
{
long long left = 0, right = MAX;
z = 100 * y / x;
if (z >= 99)
left = -1;
else
{
while (left <= right)
{
long long middle = (left + right) / 2;
long long cal = 100 * (y + middle) / (x + middle);
if (cal <= z)
left = middle + 1;
else
right = middle - 1;
}
}
cout << left << '\n';
}
return 0;
}
2019-02-16 01:05:19에 Tistory에서 작성되었습니다.