문제 풀기

Rasmus와 Ryan은 방금 Chalmers Challenge 2067에 참가했다. 주최자인 Joshua는 점점 더 야심이 커져 이제 AI를 사용해 방대한 양의 문제를 생성한다. 무한한 AI 클러스터를 사용할 수 있으므로 대회의 제한 시간을 완전히 없앴다! 대회는 그저 참가자가 막힐 때까지 계속된다.

오늘 대회를 위해 Joshua는 문제 $N$개를 선정했다. 대회를 더 흥미롭게 만들기 위해 Joshua는 일부 문제가 서로 이어지도록 하는 선행 조건을 도입했다. 예를 들어 Chalmers Coin 2을 시작하려면 먼저 Chalmers Coin 1을 풀어야 한다.

각 문제 $i$에는 선행 조건 $P_i$이 있다. $P_i = 0$이면 문제를 즉시 시작할 수 있고, 그렇지 않으면 문제 $i$에 도전하기 전에 문제 $P_i$을 풀어야 한다.

문제 $i$을 풀면 $S_i$점을 얻는다.

Rasmus와 Ryan은 고집이 세서 현재 문제를 풀기 전까지 다음 문제로 넘어가기를 거부한다. 이는 각 문제 $i$에서 Rasmus가 막혀 대회를 끝내야 할 위험이 있으며, 그 위험이 $A_i\%$임을 뜻한다. Ryan이 같은 문제에서 막힐 위험은 $B_i\%$이다.

참가자가 막히면 해당 문제에서 $0$점을 받고 포기하며, 더 이상 어떤 문제에도 도전할 수 없다. 각 문제에서 실패할 위험은 서로 독립적이다.

Rasmus와 Ryan은 알고리즘 전문가이므로 둘 다 최적으로 경쟁한다. 이들은 선행 조건을 지키면서 도전할 문제의 순서를 선택하여 자신의 기댓값 점수를 최대화한다. (비공식적으로, 어떤 순서의 기댓값 점수란 그 순서를 매우 여러 번 다시 수행했을 때 얻게 되는 점수의 평균이다.)

Rasmus와 Ryan 중 누가 더 높은 기댓값 점수를 얻을지, 또는 동점인지를 계산하는 프로그램을 작성하라.

채점

제출한 프로그램은 여러 테스트 그룹으로 이루어진 테스트 세트로 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$5$| 하나의 사슬 ($P_i = i - 1$).

$2$ |$5$| 루트에서 시작하는 사슬이 최대 두 개.

$3$ |$20$| 선행 조건 없음 ($P_i = 0$).

$4$ |$10$| 사슬들의 포리스트 (각 문제는 최대 하나의 다른 문제에 대한 선행 조건이다).

$5$ |$5$| $N \leq 10$

$6$ |$5$| $N \leq 1000$이고 모든 $i$에 대해 $A_i = B_i = 50$.

$7$ |$15$| $N \leq 1000$

$8$ |$35$| 추가 제약 조건 없음.

첫째 줄에 대회의 문제 수를 나타내는 정수 $N$가 주어진다. ($1 \leq N \leq 2 \cdot 10^5$)

이어지는 $N$개의 각 줄은 문제 $1$부터 문제 $N$까지 하나의 문제를 설명한다. 이 중 $i$번째 줄에는 네 정수 $S_i, P_i, A_i$와 $B_i$가 주어진다. ($1 \leq S_i \leq 1000$, $0 \leq P_i < i$, $1 \leq A_i, B_i \leq 99$) 이는 각각 문제 $i$을 풀면 얻는 점수, 그 문제의 선행 조건, Rasmus와 Ryan이 그 문제에서 막힐 위험이다.

더 높은 기댓값 점수를 얻는 사람에 따라 Rasmus'' 또는 Ryan''을 출력한다. 두 사람의 기댓값 점수 차이가 $10^{-6}$ 이하라면 ``Tie''를 출력한다.

부동소수점 문제를 피하기 위해 두 기댓값 점수는 정확히 같거나, 두 점수의 절댓값 차이가 적어도 $10^{-5}$임이 보장된다.

Rasmus와 Ryan이 막힐 위험은 같다. 두 사람은 먼저 문제 1에 도전한 다음 문제 2에 도전해야 하며, 이때 기댓값 점수는 다음과 같다. $0.5 \cdot 0 + 0.5 \cdot (0.1 \cdot 10 + 0.9 \cdot 30) = 14$. 둘의 기댓값 점수가 같으므로 결과는 ``Tie''이다.

이 대회에는 문제가 하나뿐이다. Rasmus가 이 문제에서 막힐 위험은 $1\%$이며, 이는 문제를 풀고 $100$점을 얻을 확률이 $99\%$임을 뜻한다. 그의 기댓값 점수는 $0.99 \cdot 100 = 99$이다. Ryan이 같은 문제에서 막힐 위험은 $99\%$이며, 이는 문제를 풀 확률이 $1\%$임을 뜻한다. 그의 기댓값 점수는 $0.01 \cdot 100 = 1$이다. Rasmus의 기댓값 점수가 더 높으므로 ($99 > 1$) 출력은 ``Rasmus''이다.