algospot RATIO

문제 링크입니다: https://algospot.com/judge/problem/read/RATIO

불가능한 경우를 찾을 때 총 게임 뿐만 아니라 이긴 게임에도 L을 더해주는 것이 핵심이였습니다.

/*

싸비는 윈도우XP 운영체제에 포함되어 있는 스파이더 카드게임을 매우 좋아한다.

처음에는 지는 경우가 있었는데, 점점 연습을 함에 따라 필승법을 발견하였고 매번 승리를 하게 되었다.

스파이더 게임을 하면 플레이어에 대한 정보가 다음과 같이 주어지는데 싸비는 이것을 보다 표시되고 있는

승률을 1 % 이상 올리기 위해선 최소한 몇 번의 연승이 필요한지 의구심이 들었다.

 

플레이 횟수 : N

승리 횟수 : M(Z %)

 

여기서 Z%의 경우 소수점을 제외한 부분의 승률이다.즉, 승률이 88.68% 일 경우 Z = 88 % 이다.

N, M이 주어졌을 때, Z를 올리기 위한 최소한의 연승횟수가 필요한지 구하는 프로그램을 작성하라.

여기서 답이 되는 연승횟수는 2,000,000,000 이하라고 가정한다.

*/

#include <iostream>

using namespace std;

 

//최대 게임 수

const long long L = 2000000000;

 

long long N, Win; //총 게임수, 이긴 게임수

 

//b 게임 중 a 게임 승리했을 때의 승률

int ratio(long long b, long long a)

{

        return (a * 100) / b;

}

 

//최소 몇 연승해야 승률이 올라갈까?

int neededGames(long long games, long long won)

{

        //불가능한 경우를 미리 걸러낸다

        if (ratio(games, won) == ratio(games + L, won + L))

               return -1;

       

        long long low = 0, high = L;

        //반복문 불변식

        //1. low 게임 이기면 승률은 변하지 않는다

        //2. high 게임 이기면 승률은 변한다

        while (low + 1 < high)

        {

               long long mid = (low + high) / 2;

               if (ratio(games, won) == ratio(games + mid, won + mid))

                       low = mid;

               else

                       high = mid;

        }

        return high;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> N >> Win;

               if (N < 1 || N>1000000000 || Win<0 || Win>N)

                       exit(-1);

 

               cout << neededGames(N, Win) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략