codeforces #592 div2 C - The Football season(수학, 발상)

https://codeforces.com/contest/1244/problem/C

 

n <= 1e12, p <= 1e17, d<w<=1e5

 

n과 p의 범위가 너무 넓어서 탐색범위를 이분탐색으로 줄여보려고 했지만 실패했다.

 

editorial 풀이)

d번 이겼을 때 : wd point

w번 비겼을 때 : wd point 

위와 같이 두 경우의 경우 얻는 포인트가 동일하다.

이걸 이용해서 비긴 횟수 y가 w보다 큰 경우, 

(1)  x번 이겼을 떄 : point1  // y번 비겼을 떄 : point2

상황을 다음과 같이 바꿀 수 있다.

(2) x+d번 이겼을 때 : point1 + wd  //  y-w번 비겼을 떄 : point2 - wd

1,2번 상황은 모두 점수의 합이 같다.

 

위 로직을 y가 w보다 작을 떄 까지 반복할 수 있으므로, 가능한 y의 범위를 w이하로 강제할 수 있다.

-> O(1e5)

 

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ll n, p, w, d;
	cin >> n >> p >> w >> d;
	ll x, y=-1;
	for (ll i = 0; i < w; i++) {
		if (p - i * d >= 0 && (p - i * d) % w == 0) {
			if ((p - i * d) / w + i <= n) {
				y = i;
				x = (p - i * d) / w;
				break;
			}
		}
	}
	if (y == -1) cout << -1 << '\n';
	else cout << x << " " << y << " " << n - x - y << '\n';
}

p-i*d는 y가 i일 때 wx를 의미한다. (wx + dy = p)