개인공부용123 프로그래밍 블로그

AlgoSpot) RATIO 본문

알고리즘문제

AlgoSpot) RATIO

개인공부용123 2017. 2. 13. 22:37

문제 : https://algospot.com/judge/problem/read/RATIO


플레이한 횟수 N, 승리 횟수 M 일떄 몇연승을 했을경우 승리율을 높일수있는지 찾는 문제이다 

(승리율은 승리횟수 / 플레이한 횟수를 한 정수이다)


연승한 횟수 + 승리 횟수 / 연승한 횟수 + 플레이한 횟수 와 승리 횟수 / 플레이한 횟수를 비교해서 이분법을 사용해서 답을 찾으면 됩니다.

(문제를 풀때 decision함수의 인자로 long long을 사용하지않으면 범위를 초과해서 결과가 나오지않습니다.)




#include 

using namespace std;

#define MAX_SWIN 2000000000

long N, M; // 플레이횟수, 승리횟수

int decision(long long s_win, long long total) {
	return (s_win * 100) / total;
}

long optimize() {
	long lo = 0, hi = MAX_SWIN;
	
	if (decision(M , N) == decision(M + hi, N + hi)) return -1;

	while (lo + 1 < hi) {
		long mid = (lo + hi) / 2;
		
		if (decision(M, N) < decision(M + mid, N + mid)) hi = mid;
		else lo = mid;
	}

	return hi;
}

int main() {
	ios::sync_with_stdio(false);

	int C;
	cin >> C;
	
	while (C--) {
		cin >> N >> M;

		cout << optimize() << endl;
	}

	return 0;
}

'알고리즘문제' 카테고리의 다른 글

AlgoSpot) PASS486  (0) 2017.02.20
AlgoSpot) POTION  (0) 2017.02.20
AlgoSpot) LOAN  (0) 2017.02.07
AlgoSpot) CANADATRIP  (0) 2017.02.06
AlgoSpot) ARCTIC  (0) 2017.02.03