[CDJ] 2017 Round 1B - A. Steed 2: Cruise Control

문제 링크

CodeJam 2017 Round 1B A번 문제 Steed 2: Cruise Control

[CodoeJam]

출처 : https://code.google.com/codejam/contest/8294486/dashboard#s=p0

[백준 알고리즘]

참고(Small) : https://www.acmicpc.net/problem/14797 

참고(Large) : https://www.acmicpc.net/problem/14804

문제 요약

- Annie는 말을 타고 한 줄로된 길을 달린다.

- Annie의 시작 위치는 0 이고 목적지는 D 킬로미터 떨어져 있다. 

- Annie와 목적지 사이에는 N 마리의 말이 있다.

- N마리의 말은 각각 K(i) 위치에 시간 당 최대 S(i)로 달릴 수 있다.

- 말들은 자신보다 앞에 있는 말보다 속도가 빨라 따라잡을 경우 이전 말의 속도와 일정하게 달린다.

- Annie가 다른 말을 앞서가지 않고 목적지까지 일정한 속도로 달릴 때 가능한 최대 속도는?

입출력

입력 

T(테스트 케이스 수)

D(목적지 위치) N (말의 수)

K(i) S(i) (i번째 말의 위치와 속도) -> N번 반복

출력

각 테스트 케이스는 "Case #x:" 로 표시하며 그 다음 줄에 결과를 출력한다.

Annie의 말이 달릴 수 있는 최대 속도를 출력한다.

Limits

1 ≤ T ≤ 100.
0 < K_i < D ≤ 10⁹, for all i.
K_i ≠ K_j, for all i ≠ j. (No two horses start in the same position.)
1 ≤ S_i ≤ 10000.

Small dataset

1 ≤ N ≤ 2.

Large dataset

1 ≤ N ≤ 1000.

예제 입력

3
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

예제 출력

Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

문제 해설

이 문제는 Annie 앞의 말 중 목적지까지 달릴 때 걸리는 시간이 최대인 말을 구하면 되는 문제이다.

목적지까지 달리는 시간이 최대인 말을 뒷 말이 절대 앞설 수 없으므로 

Annie가 목적지까지 도달할 수 있는 최소 시간은 목적지까지 달리는 시간이 최대인 말의 시간과 같다.

따라서 Annie의 최대 속도는 아래와 같다.

결국 목적지 까지 달릴 때 걸리는 시간이 최대인 말의 시간만 찾으면 되므로 O(N)의 시간 복잡도를 가진다.

소스 코드