| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 206 | 69 | 66 | 46.154% |
당신은 잃어버린 문명에 대해 연구하는 고고학자이다. 당신이 연구하고 있는 문명은 다음과 같은 특징을 갖는다.
즉, 잃어버린 문명은 트리 구조를 이루고 있다.
문명에서의 외곽 도시는 연결된 도로의 수가 정확히 하나인 도시로 정의된다. 또한, 도시의 안정성은 그 도시에서부터 가장 가까운 외곽 도시까지의 거리로 정의된다. 이때, 두 도시 사이의 거리는 한 도시에서 다른 도시로 이동하기 위해 지나야 하는 도로 개수의 최솟값으로 정의된다. 정의에 의해, 모든 외곽 도시의 안정성은 0ドル$이다.
당신은 이 문명에 대한 새로운 가설을 세웠다. 이는 어떤 배열 $[A_1, A_2, \cdots, A_N]$에 대하여, 모든 1ドル \le i \le N$에 대해 $i$번 도시의 안전성은 $A_i$ 이상이라는 것이다.
$N$과 $[A_1, A_2, \cdots, A_N]$이 주어졌을 때, 가설을 만족하는 문명이 있는지 판별하고, 만약 존재한다면 조건을 만족하는 아무 문명을 출력하라.
첫 번째 줄에 문명을 이루는 도시의 수를 나타내는 정수 $N$이 주어진다.
두 번째 줄에는 정수 $A_1, A_2, \cdots, A_N$이 순서대로 공백으로 구분되어 주어진다.
만약 주어진 가설을 만족하는 문명이 존재한다면, $N-1$줄에 걸쳐 문명을 구성하는 도로에 대한 정보를 출력해야 한다.
$i$번째 줄에는 두 정수 $a_i$와 $b_i$를 공백을 사이에 두고 출력해야 하는데, 이는 문명에 $a_i$번 도시와 $b_i$번 도시를 연결하는 도로가 있음을 의미한다.
만약 주어진 가설을 만족하는 문명이 존재하지 않을 경우, 첫 줄에 $-1$을 출력해야 한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $N \le 3$ |
| 2 | 6 | 모든 1ドル \le i \le N$에 대해 $A_i \le 1$ |
| 3 | 82 | 추가적인 제약 조건이 없다. |
4 1 0 0 0
1 2 1 3 1 4
예제 출력에서, 2,ドル 3, 4$번 도시가 외곽 도시이다. 따라서 이 도시들의 안정성은 0ドル$이다.
1ドル$번 도시의 경우, 가장 가까운 외곽 도시까지의 거리가 1ドル$이므로 안정성이 1ドル$이다.
따라서 모든 1ドル \le i \le N$에 대해 $i$번 도시의 안정성은 $A_i$ 이상이므로 주어진 가설을 만족한다.
7 2 1 1 0 0 0 0
1 2 1 3 1 4 2 5 3 6 4 7
예제 출력에서, 안정성이 2ドル$인 도시는 1ドル$번 도시가 유일하고, 2,ドル 3, 4$번 도시는 안정성이 1ドル$이다. 나머지 도시들은 안정성이 모두 0ドル$이다.
가설을 만족하는 다른 문명이 있을 수 있음에 유의하라.
4 1 2 3 4
-1
가설을 만족하는 문명이 존재하지 않는다.
University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest C번