| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 130 | 85 | 66 | 61.111% |
창하는 이번 학기에 '뉴스와미디어'라는 영어 과목을 수강하고 있다. '뉴스와미디어'에서는 단어 퀴즈를 보는데, 선생님은 단어장에 있는 $N$($N$은 4ドル$의 배수)개의 단어를 4ドル$개의 분반에 겹치지 않게 $\cfrac{N}{4}$개씩 나누어 출제하려고 한다. $i$번째 단어 $S_i$는 난이도 $D_i$를 가지고 있으며, 분반에는 1ドル$부터 4ドル$까지의 번호가 붙어있다. 이때 각 분반이 받는 스트레스는 해당 분반이 퀴즈를 보는 단어들의 난이도 중 최댓값으로 정의한다. 선생님은 형평성을 위해 4ドル$개 분반의 스트레스 중 최댓값과 최솟값의 차이를 최소화하려고 한다. 이때 선생님이 어떻게 단어를 배정해야 좋을지 알려주자!
첫 번째 줄에 정수 $N$$(4 \le N \le 2\times 10^5;$ $N$은 4ドル$의 배수$)$이 주어진다.
다음 $N$개의 줄 중 $i$번째 줄에 알파벳 소문자로 이루어진, 길이가 1ドル$ 이상 10ドル$ 이하인 단어 $S_i$와 난이도를 나타내는 정수 $D_i$ $(1 \le D_i \le 10^9)$가 공백으로 구분되어 주어진다. 1ドル\le i < j \le N$인 모든 $i,ドル $j$에 대해 $S_i \ne S_j$가 성립한다.
총 4ドル$개의 줄에 걸쳐 $i$번째 줄에 정수 $i$와 공백 하나를 출력하고 $i$번 분반 퀴즈에 배정할 $\cfrac{N}{4}$개의 단어들을 공백으로 구분하여 출력한다. 이때 단어들은 사전순으로 출력한다.
정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.
8 abate 1 abstinent 2 ambience 2 aptitude 3 audacity 2 benign 1 burlesque 4 capricious 3
1 ambience burlesque 2 abstinent capricious 3 aptitude benign 4 abate audacity
School > 한국과학영재학교 > 2025 Spring Automata 창하컵 A번