레벨 업
플래티넘 I의견: 0
여러분은 \(N\)명의 게임 캐릭터를 육성하려고 한다. \(i\) (\(1 ≤ i ≤ N\)) 번째 캐릭터의 현재 레벨은 \(L_i\)이다.
캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 \(M\)번 진행할 것이다.
- 레벨이 낮은 순서대로 \(K\)명의 캐릭터를 선택한다. 레벨이 같은 캐릭터가 여러 명일 경우 그 중 아무 캐릭터나 선택한다.
- 선택된 캐릭터들의 레벨을 각각 \(1\)만큼 올린다.
예를 들어, \(M = 4\), \(K = 3\)이고 \(N = 5\)명의 캐릭터의 레벨이 각각 \(5\), \(1\), \(7\), \(5\), \(4\)라고 하자. 트레이닝을 한 번 진행하면 \(2\), \(4\), \(5\)번째 캐릭터의 레벨이 오르고, 이때 캐릭터의 레벨은 각각 \(5\), \(2\), \(7\), \(6\), \(5\)가 된다.
위의 예시에서 각 트레이닝을 진행한 이후 캐릭터의 레벨은 다음과 같다.
| 트레이닝 횟수 | 캐릭터의 레벨 |
|---|---|
| \(1\) | \(5\), \(2\), \(7\), \(6\), \(5\) |
| \(2\) | \(6\), \(3\), \(7\), \(6\), \(6\) |
| \(3\) | \(7\), \(4\), \(7\), \(6\), \(7\) |
| \(4\) | \(7\), \(5\), \(8\), \(7\), \(7\) |
\(M\)번의 트레이닝이 모두 끝난 이후 N명의 캐릭터의 레벨을 오름차순으로 출력하는 프로그램을 작성하시오.
- \(1 \le N \le 100\,000\)
- \(1 \le M \le 10^9\)
- \(1 \le K \le N\)
- \(1 \le L_i \le 10^9\) (\(1 \le i \le N\))
첫 번째 줄에 캐릭터의 수를 나타내는 정수 \(N\)이 주어진다.
두 번째 줄에 각 캐릭터의 레벨을 나타내는 정수 \(L_1, \dots , L_N\)이 공백으로 구분되어 주어진다.
세 번째 줄에 정수 \(M\), \(K\)가 공백으로 구분되어 주어진다.
첫 번째 줄에 모든 트레이닝이 끝난 이후 캐릭터들의 레벨을 오름차순으로 정렬하여 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 4점 | \(N \le 1\,000\), \(M \le 1\,000\). |
2 | 10점 | \(K = 1\). |
3 | 32점 | \(M \le 100\,000\). |
4 | 54점 | 추가 제약 조건 없음. |
5
5 1 7 5 4
4 3
5 7 7 7 8
4
7 4 2 9
10 1
7 8 8 9
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 2차 대회 > 중등부 4번 / 고등부 3번
평가 및 의견
레벨 업
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
레벨 업