[[problem:RATIO]] 문제 풀이 중 입니다.
예제의 답은 잘 나오는데 고려하지 못한 케이스가 있는 것인지 오답이 뜹니다.
코드 리뷰 부탁 드립니다.
풀이는 이분법을 써서 0 ~ 2000000000 범위 내에서 검색하는 것 입니다.
upper 는 항상 가능한 답을 갖고 있고요.
-1 처리는 목표 승률이 100을 넘을 때라고 생각 했습니다.
입력 범위 내에서 2000000000 연승이면 무조건 1% 는 올릴 수 있기 때문에
그 외에 -1 이 출력되어야 할 경우는 없을 것 같습니다.
#include <iostream>
#include <cmath>
using namespace std;
long long solve(long long N, long long M, int target);
int main() {
int T;
cin >> T;
while (T-->0) {
long long N, M;
cin >> N >> M;
int target_ratio = (double)M / N * 100 + 1;
if (target_ratio > 100)
cout << -1 << endl;
else
cout << solve(N, M, target_ratio) << endl;
}
return 0;
}
long long solve(long long N, long long M, int target) {
long long lower = 0;
long long upper = 2000000000;
while (lower + 1 < upper) {
long long mid = (lower + upper) / 2;
int ratio = (double)(M+mid) / (N+mid) * 100;
if (ratio < target) {
lower = mid;
}
else if (ratio >= target) {
upper = mid;
}
}
return upper;
}
문제를 보면 "여기서 답이 되는 연승횟수는 2,000,000,000 이하라고 가정한다." 이기 때문에 2,000,000,000 연승이면 무조건 1%를 올릴 수 있을 것이고, 1%를 올릴 수 없는 경우는 이미 100% 일 경우라고 생각했습니다. 그리고 실제 N의 입력 범위도 1~1,000,000,000 이기 때문에 2,000,000,000 이면 적어도 1%는 무조건 올릴 수 있고요.. 구체적인 힌트를 부탁 드려도 될까요? ㅠ.ㅠ
kwangswei
[[problem:RATIO]] 문제 풀이 중 입니다.
예제의 답은 잘 나오는데 고려하지 못한 케이스가 있는 것인지 오답이 뜹니다.
코드 리뷰 부탁 드립니다.
풀이는 이분법을 써서 0 ~ 2000000000 범위 내에서 검색하는 것 입니다.
upper 는 항상 가능한 답을 갖고 있고요.
-1 처리는 목표 승률이 100을 넘을 때라고 생각 했습니다.
입력 범위 내에서 2000000000 연승이면 무조건 1% 는 올릴 수 있기 때문에
그 외에 -1 이 출력되어야 할 경우는 없을 것 같습니다.
12년 전