[ALGOSPOT] RATIO 승률 올리기

ALGOSPOT RATIO : https://algospot.com/judge/problem/read/RATIO

알고리즘 책의 수치해석 부분에 있는 문제이다

1%를 올리기 위한 최소로 이긴 게임의 수를 구해야한다

1. Rear와 Front를 이용하여 중간값을 구한다

2.새로운 승률 - 원래 승률 >1 이면 

   =>조금 더 적은 경기를 이겨야 한다 따라서 Rear = Middle

  새로운 승률 - 원래 승률 ==0 이면 

  =>더 많은 경기를 이겨야 한다 따라서 Front = Middle 

3. Rear의 값이 Front보다 1더 많다면 최소로 이겨야하는 게임의 수가 도출된다

4. 이 때 Front는 1%가 오르기 전의 최대 이긴 게임의 수 이고

         Rear는 1%가 오른 최소 이긴 게임의 수이다

예외 ) 최대로 이길수 있는 경우를 모두 이겼지만 승률이 오르지 않는다

       승률이 100% & 99%

       => 승률이 100%이면 더이상 올릴 승률이 존재하지 않는다

       => 승률이 99%이면 1%의 승률을 올리면 100%가 된다

           100%의 승률은 한번도 진 게임이 없다는 의미 이지만 이미 진 게임이 존재하므로 1%를 올릴 수 없다

#include <iostream> #include <fstream> using namespace std; long long denominator, numerator, Rear, Front; int Ratio(long long denominator, long long numerator) { return ((numerator * 100) / denominator); } void Calculate_Ratio(int Win_Count) { if ((Ratio(denominator + Win_Count, numerator + Win_Count) == Ratio(denominator, numerator)) || Ratio(denominator, numerator) == 100 || Ratio(denominator, numerator) == 99) { Rear = -1; } else { while (Rear>Front + 1) { long long Mid = (Rear + Front) / 2; if (Ratio(denominator + Mid, numerator + Mid) == Ratio(denominator, numerator)) { Front = Mid; } else { Rear = Mid; } } } } int main() { int For_Count; cin >> For_Count; for (int i = 0; i < For_Count; i++) { cin >> denominator >> numerator; Rear = 2000000000; Front = 0; Calculate_Ratio(Rear); cout << Rear << endl; } }

+) 유사문제 : RUNNINGMEDIAN