페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3395

미션 임파서블 1s 512MB

문제

첩보요원 정원, 딧불, 동현 이 셋은 그들의 비밀 코드가 일치하는지 확인하기 위해 한 카페에서 모이기로 했다. 

이들은 비밀리에 움직여야만 하므로, 만나는 시간을 정하지 않고, 각각 [0,S]사이의 한 시간에 만나기로 했다. 

각 요원은 [0,S]사이의 어떤 시간을 완전히 랜덤으로 정하며, 이를 각각 t_a, t_b, t_c로 부른다.

코드 확인은 다음과 같이 진행된다. 제일 처음 도착한 요원이 자신에게 미리 정해진 시간동안 다음 요원을 기다린다. 

만약 두 요원이 카페에서 만나면, 둘은 코드를 확인하고, 먼저 와 있던 요원은 곧바로 카페를 조용히 나간다. 

마찬가지로, 두 번째 요원은 자신에게 미리 정해진 시간동안 셋째 요원을 기다리다가, 

그 요원이 오면 서로 코드를 확인한다. 

코드 확인은 시간이 걸리지 않는다고 가정한다.

정원, 딧불, 동현이 카페에서 대기하는 시간은 W_a, W_b ,W_c로 이미 정해져 있다. 

t_a, t_b, t_c [0,S]에서 난수로 정해진 실수(Real Number)이지만 

W_a, W_b, W_c는 요원들이 각자 정해놓은 정수 시간임에 유의한다.

다음의 그림 중 Case-1과 Case-4는 코드 확인에 성공한 경우이며, Case-2와 Case-3은 실패한 경우이다. 

Case-1의 경우 정원(A)이 도착하고 W_a만큼 지나기 전에 딧불(B)이 T_b에 도착한다. 

이 때 코드 확인을 하고 정원(A)은 유유히 빠져나간다. 

마찬가지로 딧불이 T_b에 도착하고, W_b만큼의 시간이 흐르기 전에 동현(C)이 도착하므로, 

코드 확인이 제대로 진행된 모습이다. 

Case-2의 경우 딧불(B)과 동현(C)의 코드 확인이 실패한 모습이고, 

Case-3의 경우 정원(A)과 딧불(B)의 확인이 실패했다.

 

여기까지의 스토리를 보면, 코드 확인의 성공률은 네 정수 (S,W_a,W_b,W_c) 에 달려 있음을 알 수 있다. 이러한 스토리가 n개 있을 경우, 우리는 이 스토리들을 성공률을 기반으로 오름차순 정렬하고 싶다. 이러한 프로그램을 작성하라.

 


입력

첫 줄에 스토리의 개수인 n(3 <= n <= 20)이 주어진다. 둘째 줄부터 다음 n줄에 걸쳐, 각 스토리를 기초하는 네 정수가 S W_a W_b W_c 의 형태로 주어진다. (0 < W_a+W_b, W_b + W_c, W_c + W_a < S, 0 < S < 1,000)

출력

한 줄에 걸쳐, 성공률이 낮은 스토리부터 높은 스토리까지 오름차순으로 정렬한다. 만약 두 스토리가 성공률이 같다면, 더 낮은 번호의 스토리부터 출력한다.

예제 #1

3

100 12 13 14
110 8 9 15
200 23 30 40
2 1 3

예제 #2

6

201 15 16 16
375 30 32 27
900 75 73 67
203 16 17 16
373 31 32 27
895 73 75 66
1 2 3 6 5 4

출처

ACM-ICPC Seoul Regional 2018

로그인해야 코드를 작성할 수 있어요.