#Educational Codeforces Round 72 B - Zmei Gorynich

문제 링크 => Dashboard - Educational Codeforces Round 72 (Rated for Div. 2) - Codeforces

Dashboard - Educational Codeforces Round 72 (Rated for Div. 2) - Codeforces

---

어제 밤에 ICPC 학회분들과 virtual 을 돌려서 푼 문제인데 뇌절을 계속해서 풀지 못한 문제이다.

 

 

이러한 용의 머리의 길이 x 가 주어질 때 n 개의 Query가 주어진다.

 

Query 는 머리의 길이를 d 만큼 잘라낼 수 있는 d 값과 자른 후에 h 만큼 다시 생겨나는 h 값이 주어진다.

 

이 때 용의 머리를 완전하게 잘라낼 수 있는 경우 최소로 자른 횟수를 출력하고 그렇지 못한 경우 -1을 출력하는 문제이다.

 

일단 단순하게 생각하면 잘라낼 수 있는 d 값에 대하여 d >= x 일 경우 용의 머리는 단 한번에 잘라낼 수 있다는 것은 확실하다.

 

그렇다면 d < x 인 경우인데 용의 머리를 최소로 자르기 위해서 자를 수 있는 방법은 다음과 같다.

 

n 개의 Query 에서 d 값의 최대와 (d - h) 값의 최대를 저장한다.

 

편의상 maxD = max( d1, d2, ... , dn ), maxDiff = max( d1 - h1, d2 - h2, ... , dn - hn ) 라고 할 때, 

 

(1) maxD >= x 인 경우 ) 1을 출력

 

(2) maxDiff == 0 인 경우 ) 잘랐다가 늘어났다가 무한히 반복하는 경우이다. 즉, -1 출력

 

(3) 그 외의 경우 ) 한번에 잘라지지도 않고 무한히 반복하는 경우도 아닌 자를 수 있는 횟수가 정해져 있는 경우이다.  즉, (x - maxD) / maxDiff + 1 + ((x - maxD) % maxDiff == 0 ? 0 : 1) 값을 출력하며 답이다.

식이 좀 복잡한데 직접 해보니깐 이런 규칙성이 보였다.

 

뇌절하기 굉장히 좋은 문제인거 같다.

 

첨에 d, d-h 가 pair 한 상태로 계속 찾다보니 틀렸는데 다른 분들 풀이를 보니깐 한번에 d, d-h의 max값을 구해서 바로 구하는 풀이였다.

 

아무래도 코드포스는 너무나도 어렵다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

void test() {

	ll n, x, maxD, maxDiff;
	maxD = maxDiff = -1e18;
	cin >> n >> x;

	for (int i = 0; i < n; i++) {
		ll d, h;
		cin >> d >> h;
		maxD = max(maxD, d);
		maxDiff = max(maxDiff, d - h);
	}

	if (maxD >= x) cout << 1 << endl;
	else if (maxDiff <= 0) cout << -1 << endl;
	else cout << (x - maxD) / maxDiff + 1 + 
		((x - maxD) % maxDiff == 0 ? 0 : 1) << endl;

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while (t--) {
		test();
	}

	return 0;
}