Problems
여러분은 N명의 게임 캐릭터를 육성하려고 한다. i(1 ≤ i ≤ N)번째 캐릭터의 현재 레벨은 Li 이다.
캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 M번 진행할 것이다.
• 레벨이 낮은 순서대로 K명의 캐릭터를 선택한다. 레벨이 같은 캐릭터가 여러 명일 경우 그중 아무 캐릭터나 선택한다.
• 선택된 캐릭터들의 레벨을 각각 1만큼 올린다.
예를 들어, M = 4, K = 3이고 N = 5명의 캐릭터의 레벨이 각각 5, 1, 7, 5, 4라고 하자.
트레이닝을 한 번 진행하면 2, 4, 5번째 캐릭터의 레벨이 오르고, 이때 캐릭터의 레벨은 각각 5, 2, 7, 6, 5가 된다.
위의 예시에서 각 트레이닝을 진행한 이후 캐릭터의 레벨은 다음과 같다.
M 번의 트레이닝이 모두 끝난 이후 N 명의 캐릭터의 레벨을 오름차순으로 출력하는 프로그램을 작성하시오.
[제약 조건]
• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 109
• 1 ≤ K ≤ N
• 1 ≤ Li ≤ 109 (1 ≤ i ≤ N)
Input
첫 번째 줄에 캐릭터의 수를 나타내는 정수 N이 주어진다.
두 번째 줄에 각 캐릭터의 레벨을 나타내는 정수 L1, ···, Ln이 공백으로 구분되어 주어진다.
세 번째 줄에 정수 M, K가 공백으로 구분되어 주어진다.
Output
첫 번째 줄에 모든 트레이닝이 끝난 이후 캐릭터들의 레벨을 오름차순으로 정렬하여 출력한다.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 4 | |
| #2 | 10 | |
| #3 | 32 | |
| #4 | 54 | 추가 제약 조건 없음 |
Example #1
5
5 1 7 5 4
4 3
5 7 7 7 8
Example #2
4
7 4 2 9
10 1
7 8 8 9
Source
KOI 2차 2022 중4/고3
You must sign in to write code.