[수치 해석][이분법] RATIO 승률 올리기

1. 이분법

 

이 문제는 간단히 수학식으로 표현할 수 있다.

 

Z = M*100 / N

Zx = (M+x) * 100 / (N+x)

 

Z < Zx

 

이식을 조건으로 하는 이분법을 사용하면

 

Z < Zx<= Z+1 

 

가 되는 x값을 구할 수 있다.

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
 
long long T, N, M, Z;
 
int bi()
{
    long long lo = -1ll, hi = 2000000001ll;
    for(;lo + 1 < hi;)
    {
        long long mid = (lo+hi)/2ll;
        if((M*100/N) < 100*(M+mid)/(N+mid)) hi = mid;
        else lo = mid;
    }
    if(hi ==  2000000001ll) hi = -1;
    return hi;
}
 
int main()
{
    std::cin>>T;
 
    for(int i = 0; i < T; i++)
    {
        std::cin>>N>>M;
        std::cout<<bi()<<"\n";
    }
}

 

 

2. 수학적 해법

 

Z = M*100 / N

Zx = (M+x) * 100 / (N+x)

 

Z < Zx<= Z+1  이 되는 Zx는 최저 Z+1이다.

 

R = Z+1 이라 하자

 

Zx >= R

 

(M+x) * 100 >= (N+x)*R

 

x에 대해 정리하면

 

(100 - R)x >= RN - 100M

 

x >= (RN - 100M) / (100 - R) 

 

x는 정수이므로 오른쪽 분수에 올림하면 

최저 x를 구할 수 있다.

 

long long foo()
{
    long long R = (M*100/N) + 1;
    if(N==M ||R == 100)return -1;
    return (long long)ceil((long double)(R*N-100*M)/(100-R));
}

RATIO