시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 188 | 45 | 39 | 24.074% |
민철이는 국내 최고의 공원인 'Minchul Park'의 설립자이자 주인이다. 민철이는 다가오는 겨울 시즌을 기념하여 공원에서 $M$개의 축제를 개최할 예정이다. 축제가 일어난다는 소식을 들은 전국 각지의 수많은 팀들이 Minchul Park에서 공연하기 위해 오디션에 참가했다. 민철이는 오디션 결과에 따라 각 팀에 '감동 수치'를 부여했다. 각 팀의 감동 수치는 $0$ 이상 $N$ 이하의 정수이다. 감동 수치가 $i$인 팀은 관객들에게 $K^i$만큼의 감동을 줄 수 있다. 민철이는 다음 두 조건을 만족하도록 $M$개의 축제에 이 팀들을 적절히 배치하려고 한다.
이 때, 하나의 축제에서 줄 수 있는 감동의 최대 크기를 구하여라.
첫 번째 줄에는 세 정수 $N, M, K$가 공백으로 구분되어 입력된다. $(0 \leq N \leq 10^6, 1 \leq M \leq 10^{9}, 2 \leq K \leq 10)$
두 번째 줄에는 '감동 수치'가 $i(0 \leq i \leq N)$인 팀의 수인 $A_i(0 \leq A_i \leq 10^{9})$가 입력된다.
하나의 공연에서 선사할 수 있는 최대의 감동을 $K$진법으로 한 줄에 출력한다. 만약 $1$ 이상의 감동을 선사할 방법이 없다면 $0$을 출력한다. 이 경우를 제외하면 출력은 $0$으로 시작하지 않아야 한다.
3 2 2 3 1 0 1
10
감동이 $1$인 팀이 세 팀, $2$인 팀이 한 팀, $8$인 팀이 한 팀 있다. 감동이 $8$인 팀이 한 축제에 나오면 다른 축제에는 $8$ 이상의 감동을 선사할 방법이 없다. 그러므로 첫 번째 축제에는 감동이 $1$인 팀 두 팀, 두 번째 축제에는 감동이 $2$인 팀 한 팀을 올려 $2$의 감동을 주는 것이 최대 감동을 주는 방법이다. 이진수로 출력하라고 하였으므로 $10$을 출력한다.
High School > 경기과학고등학교 > 나는코더다 2022 송년대회 E번