더 나은 기회

최근 몇 년 사이 ICPC 커뮤니티의 활동 범위는 전 세계로 넓어졌습니다. 매년 111개국, 3,450개 대학, 75,000명의 팀원, 코치, 봉사자가 참여합니다. 하지만 연례 ICPC 세계 대회에 진출하는 팀은 약 130개뿐입니다. 2023 세계 대회에는 아시아 태평양 지역에서 16개 팀만 진출했습니다. 2022 ICPC 아시아 태평양 지역 대회에는 283개 대학에서 1,800개가 넘는 팀이 참가했습니다. 그중 $99\%$ 이상의 팀이 지역 대회를 넘지 못했습니다.

ICPC 아시아 태평양 지역은 2024 ICPC 세계 대회 진출팀을 고르는 새 단계로 아시아 태평양 플레이오프를 도입했습니다. 플레이오프는 지역 대회보다 높은 수준의 대회입니다. 첫 아시아 태평양 플레이오프는 2024년 베트남 하노이에서 열립니다. ICPC 아시아 태평양 규칙에 따라 약 66개 팀이 플레이오프 출전권을 얻습니다. 이번 확대로 앞으로 더 많은 팀이 높은 수준의 대회에 나갈 기회를 얻습니다.

플레이오프 도입으로 ICPC 아시아 태평양 규칙이 크게 바뀌었습니다. 새 규칙에 따르면 2023년에 지역 대회 두 곳에 참가해 플레이오프 진출 가능성을 높일 수 있습니다. 여러분의 팀은 ICPC 타오위안 지역 대회와 ICPC 자카르타 지역 대회에 나갈 계획입니다. 팀의 재계산 순위와 두 지역 대회의 사이트 점수가 주어졌을 때, 어느 지역 대회에서 진출 가능성이 더 높은지 알아내는 프로그램을 작성하시오.

(참고: 재계산 순위와 사이트 점수의 정의는 ICPC 아시아 태평양 규칙 절에 있습니다.)

첫 줄에 공백으로 구분된 네 개의 수 $R_T$, $R_J$, $S_T$, $S_J$가 주어집니다. $R_T$와 $R_J$는 타오위안 지역 대회와 자카르타 지역 대회에서 팀의 재계산 순위입니다. $S_T$와 $S_J$는 타오위안 지역 대회와 자카르타 지역 대회의 사이트 점수입니다.

타오위안 지역 대회에서 진출 가능성이 더 높으면 TAOYUAN을 출력합니다. 자카르타 지역 대회에서 진출 가능성이 더 높으면 JAKARTA를 출력합니다. 가능성이 같으면 SAME을 출력합니다.

• $R_T$와 $R_J$는 $66$보다 작은 양의 정수입니다.
• 두 지역 대회 모두에서 팀의 순위는 상위 $50\%$ 안에 있습니다.
• $1 \le S_T \le 2000$이고 $1 \le S_J \le 2000$입니다.
• $100 \cdot S_T$와 $100 \cdot S_J$는 양의 정수입니다.

다음 규칙은 남태평양(호주, 뉴질랜드 등) 팀에는 적용되지 않습니다. 남태평양 팀의 세계 대회 진출팀은 다른 아시아 태평양 지역 대회와 별도로 남태평양 독립 지역 대회에서 선발됩니다.

아시아 태평양 지역 대회의 기본 규칙

• A1. 한 팀은 최대 두 개의 지역 대회에 참가할 수 있습니다.
• A2. 지역 대회에 예선이 함께 열리면, 개최국 팀은 그 예선을 통과해야 해당 지역 대회에 나갈 수 있습니다.
• A3. 지역 대회는 아시아 태평양의 다른 나라 팀을 받아들이는 것이 기대됩니다. 각 지역 대회는 외국 팀의 상한을 정할 수 있습니다. 대회 책임자는 받아들일 외국 팀을 고르는 규칙을 정할 수 있습니다.
• A4. 지역 대회는 남태평양과 아시아 동부 같은 다른 상위 지역의 팀을 받아들일 수 있습니다. 이 팀들은 아시아 태평양 지역 대회를 통해 세계 대회에 진출하지 못합니다.
• A5. 지역 대회를 개최하는 나라의 팀은 다른 나라에서 열리는 지역 대회 두 곳에 참가하면 안 됩니다.

세계 대회 선발 규칙 (1부)

• B1. 각 지역 대회의 우승 팀은 세계 대회에 바로 진출합니다. 여기서 우승 팀은 다른 상위 지역 팀이나 남태평양 팀을 제외한 뒤 순위가 가장 높은 팀입니다.
• B2. 같은 대학의 팀 두 개 이상이 서로 다른 지역 대회에서 우승하면, 세계 대회에 진출하는 팀은 그중 하나뿐입니다. 대학이 그중 한 팀을 고릅니다. 선택에 따라 대학은 팀끼리 플레이오프를 치러 한 팀을 고르게 할 수도 있습니다. (이 팀들은 플레이오프에 초대됩니다. D1을 보시오.)
• B3. 같은 대학의 우승 팀을 플레이오프에 보내는 경우(B2 참조), 그중 플레이오프 순위가 가장 높은 팀이 다른 대학 팀들의 순위와 관계없이 세계 대회에 진출합니다.

지역 대회의 사이트 점수

• C1. 각 지역 대회의 사이트 점수 $S$는 다음과 같이 정의합니다.

$S = 0.56 \times \text{지역 대회 대학 수} + 0.24 \times \text{지역 대회 팀 수} + 0.14 \times \text{예선 대학 수} + 0.06 \times \text{예선 팀 수} + 0.30 \times \text{지역 대회 외국 팀 수}$

문제를 한 개 이상 푼 팀만 셉니다. 남태평양과 다른 상위 지역 팀도 셉니다.

(참고) 이 식은 2020년부터 적용된 아시아 태평양 세계 대회 선발 규칙에서 가져온 것입니다.

플레이오프 선발 규칙

• D1. 각 지역 대회의 우승 팀은 오픈 참가 팀으로 플레이오프에 초대됩니다. 플레이오프 성적은 세계 대회 진출에 영향을 주지 않습니다. 다만 B2와 B3 규칙 때문에 플레이오프에 나가는 팀은 예외입니다.

(참고) 우승 대학에서는 우승 팀만 플레이오프에 나갈 수 있습니다. 다른 팀(지역 대회 2위 이하)은 나갈 수 없습니다.

(참고) 우승 팀은 플레이오프 순위에 포함되지만 E1(1)에서 제외되므로, 다른 대학 팀의 진출에는 영향을 주지 않습니다.

• D2. 각 지역 대회 X의 순위에 대해 다음 단계를 순서대로 적용합니다.

  1. 남태평양과 다른 상위 지역 팀을 순위에서 뺍니다.

  2. 문제를 하나도 풀지 못한 팀을 순위에서 뺍니다. 문제를 한 개 이상 푼 팀만 남깁니다.

  3. 앞 단계 뒤에 남은 팀의 상위 50%(올림)만 남기고, 나머지 아래쪽 팀은 뺍니다. 하위 절반의 팀은 플레이오프에 나갈 수 없습니다.

     (참고) 이 단계는 드문 경우에만 작동합니다. 예를 들어 대표 팀이 적은 나라의 팀은 상위 절반에 들어야만 진출할 수 있습니다. D3(3)을 보시오.

  4. 우승 대학의 팀을 순위에서 뺍니다. 우승 대학은 지역 대회 X 또는 다른 지역 대회에서 우승 팀이 나온 대학입니다.

  5. 각 대학의 4위 이하 팀을 순위에서 뺍니다.

     (참고) 한 대학에서 플레이오프에 나갈 수 있는 팀은 최대 3개입니다. D3(2)를 보시오.

  6. 남은 각 팀의 재계산 순위 $R$을 다시 계산합니다. 각 팀에 $(R-1)/S$ 값을 부여합니다. 여기서 $S$는 지역 대회 X의 사이트 점수입니다.

     (참고) 이 정의와 다음 단계는 Shieh-Ishihata 식을 따릅니다. 이 식은 COVID-19 이전 아시아 태평양 세계 대회 선발 규칙의 핵심이었습니다.

• D3. 모든 아시아 태평양 지역 대회의 목록을 합치고 다음 단계를 순서대로 적용합니다.

  1. 합친 목록을 값의 오름차순으로 정렬합니다.

  2. 같은 팀이 두 번째로 나오면 그 항목을 지웁니다. 그다음 한 대학의 네 번째 이후 팀을 지웁니다. 그러면 한 대학에서 최대 3개 팀만 진출합니다.

     (참고) 4위 이하 팀은 D2(5)에서 이미 뺐지만, 이 단계도 필요합니다.

  3. 아시아 태평양의 각 나라에서 값이 가장 작은 팀을 하나씩 고릅니다. 그 팀이 플레이오프에 진출합니다.

     (참고) 이 와일드카드 규칙은 모든 나라에서 최소 한 팀이 나가도록 보장합니다. 다만 그 팀은 자기 지역 대회의 상위 절반에 있어야 합니다. D2(3)을 보시오.

  4. 플레이오프 진출 팀 수를 $P$라고 합시다. 값이 가장 작은 팀부터 목록을 훑으면서, 3단계에서 이미 고른 팀은 건너뛰고 $P$개 팀이 될 때까지 하나씩 고릅니다. 이 팀들이 플레이오프에 진출합니다.

• D4. 진출한 팀이 플레이오프 참가를 포기해 추가로 팀을 뽑아야 하면, 그 팀을 모든 지역 대회의 순위에서 뺀 뒤 D2를(따라서 D3도) 다시 적용합니다.

  (참고) D4에서 사이트 점수는 다시 계산하지 않습니다.

  (참고) 플레이오프 참가를 포기한 팀에게 불이익은 없습니다.

세계 대회 선발 규칙 (2부)

• E1. 세계 대회 팀은 먼저 B1부터 B3까지의 규칙으로 선발합니다. 그다음 플레이오프 순위가 가장 높은 팀을 다음 절차로 고릅니다.
  1. 플레이오프 순위에서 오픈 참가 상태의 팀(지역 대회 우승 팀)을 뺍니다.
  2. 플레이오프 순위에서 각 대학의 2위 이하 팀을 뺍니다.
  3. 아시아 태평양에 배정된 세계 대회 자리 수를 $N$, B1부터 B3에서 진출이 정해진 팀 수를 $M$이라고 합시다. 수정된 순위의 상위 $N - M$개 팀이 세계 대회에 진출합니다.