시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 94 | 7 | 7 | 20.588% |
두 명이 같이 하는 인터넷 슈팅 게임이 있다. 이 게임은 폐허가 된 도시에서 빌딩들을 부수는 게임이다. 게임에서 바닥인 수평선 위에 $N$개의 빌딩이 왼쪽에서 오른쪽으로 서 있다. 빌딩은 왼쪽에서 오른쪽으로 순서대로 1부터 $N$의 정수로 나타낸다. 각 빌딩의 바닥으로부터의 높이는 수열 $A_i$ $(1 \le i \le N)$로 나타내고, $1$부터 $N$까지의 서로 다른 정수로 주어진다.
두 명의 플레이어는 모든 빌딩보다 왼쪽의 같은 위치에 있다. 시간 $i$($\ge 1$)에 두 명의 플레이어는 동시에 각 한발씩 총을 발사하고, 총알은 발사한 위치에서 수평으로 오른쪽으로 날아간다. 두 총알의 속도는 동일하다. 플레이어는 총알의 발사 높이를 바닥으로부터의 거리 $H$로 결정한다. $H$는 $1$이상 $N+1$이하의 정수이다. 두 플레이어는 동일한 발사 높이를 선택할 수 있다.
플레이어의 총알 발사 높이가 $H$인 경우, $A_i \ge H$를 만족하는 파괴되지 않은 가장 왼쪽의 빌딩이 이 총알로 파괴된다. 이 조건을 만족하는 빌딩이 없다면, 아무 일도 일어나지 않는다. 만약 두 플레이어가 발사한 총알에 대해 이 조건을 만족하는 빌딩이 동일하다면, (두 총알의 속도는 동일하기 때문에) 이 하나의 빌딩만 파괴된다. 특별히, 두 플레이어의 발사 높이가 같다면, 항상 하나의 빌딩만 파괴된다. 예를 들어, $A_1 = 2, A_2 = 1$이고, 처음에 두 플레이어가 모두 $H = 1$을 발사 높이로 결정하였다면, 이 두 총알로 빌딩 $1$만 파괴된다.
문제는 $N$개 빌딩들의 높이가 입력으로 주어질 때, 모든 빌딩을 파괴할 수 있는 최소 시간과 각 시간에 두 플레이어의 총알 발사 높이를 찾는 것이다.
첫째 줄에 정수 $N$이 주어진다.
다음 줄에는 $N$개의 공백으로 구분된 정수 $A_1, A_2, \ldots, A_N$이 주어진다.
첫째 줄에 두 플레이어가 모든 빌딩을 파괴하기 위한 최소 시간 $T$를 출력한다.
다음 $T$개의 줄에는 공백으로 구분된 두 정수를 한 줄에 하나씩 출력한다. 두 정수는 각각 첫 번째와 두 번째 플레이어의 총알 발사 높이를 나타낸다. 두 정수는 1보다 크거나 같고, $N+1$보다 작거나 같아야 하며, 두 정수가 서로 같아도 된다.
번호 | 배점 | 제한 |
---|---|---|
1 | 17 | $1 \le i < j < k \le N$이고 $A_i < A_j < A_k$를 만족하는 $(i, j, k)$가 존재하지 않는다. |
2 | 12 | $1 \le i < j < k \le N$이고 $A_i > A_j > A_k$를 만족하는 $(i, j, k)$가 존재하지 않는다. |
3 | 9 | $N \le 4$ |
4 | 12 | $N \le 16$ |
5 | 31 | $N \le 500$ |
6 | 29 | $N \le 7\,500$ |
7 | 40 | 추가적인 제약 조건이 없다. |
4 1 2 4 3
2 1 4 2 3
8 4 3 8 2 1 7 6 5
4 4 8 3 7 2 6 1 5
8 5 6 7 1 2 8 3 4
4 5 6 7 8 1 2 3 4
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon D번
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2021 > 2차 선발고사 1번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon D번