/*
제가 생각해본 풀이방법입니다.
1. 찾아 내야할 %수치가 어떤것인지 먼저 찾습니다.
이것은(이긴횟수 / 총횟수) * 100 + 1 이라 생각했습니다.
2. left값은 1로 두었습니다.right값은 최대 이긴 횟수 N으로 두었습니다.
3. 이진 탐색을 진행했습니다.
ㄱ.value라는 변수를 사용하여 mid값에 따른 현재의 %를 계산합니다
ㄴ.value == find일경우에
min>mid 이면 min = mid로 갱신합니다.
그리고 right = mid - 1로 갱신합니다.더 작은 이긴 횟수를 찾기 위해서 입니다.
ㄷ. value<find 인경우 left = mid+1로 갱신합니다.
ㄹ. value>find 인경우 right = mid-1로 갱신합니다.
ㅁ. min의 값이 변하지 않았다면 +1%를 만드는 연승 횟수가 존재하지 않으므로 -1을 출력했습니다.
ㅂ. 그 외의 경우에는 min값을 출력하였습니다.
*/
//#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
long long N, M;
int i, j, T, k;
long long value;
long long find, min;
long long left, right, mid;
// freopen("input.txt","r",stdin);
scanf("%d", &T); // 총 횟수
for (k = 1; k <= T; k++)
{
scanf("%I64d %I64d", &N, &M); // N은 총횟수 M은 이긴 횟수
if (N == 0) //0으로 나눠질때의 예외 처리
find = 0;
else
find = (M * 100) / N;
find = find + 1; //우리가 원하는 1%가 올라간 수치. 즉 찾고자 하는 %값
min = 3000000000; // 나올 수 있는 가장 큰 값보다 큰값 설정
left = 1;
right = N; //가장 오른쪽에 있는 값을 총횟수로 지정해주었습니다.
while (1) // 이진 탐색을 통해 원하는 값을 탐색합니다.
{
if (left>right) break;
mid = (left + right) / 2;
value = ((M + mid) * 100) / (N + mid);
// 탐색된 값의 %를 확인하고 find보다 작으면 mid보다 큰위치를 탐색
// 같은경우 mid와 최소값을 비교하여 갱신
// %가 큰경우 mid보다 작은 위치 탐색
if (value == find)
{
if (min>mid)
{
min = mid;
}
right = mid - 1;
}
else if (value<find)
{
left = mid + 1;
}
else if (value>find)
{
right = mid - 1;
}
}
if (min == 3000000000)
printf("-1\n");
else
printf("%I64d\n", min);
}
return 0;
}
김동휘
10년 전