시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB (추가 메모리 없음) | 426 | 80 | 70 | 33.654% |
컴퓨터과학과의 교수님들은 학생들을 기쁘게 하기 위해 과제를 비슷한 시기에 내주신다.
이번 학기 $6$전공을 채워 넣은 태호는 교수님들의 과제 공격을 받고 정신을 못 차리고 있다.
각각의 과제는 $X_i$ 일 동안 하면 마무리가 되는데, 태호는 이틀 연속으로 똑같은 과목의 과제를 하면 일찍 질려버린다. 결국 태호는 매일 매일 다른 과목의 과제를 하기로 결정했다. 만약 $N$개의 과제를 해야 한다면, $1$일 차엔 첫 번째 과제를 하고, $2$일 차에는 두 번째 과제를 하고, ... $N$일차에는 $N$번째 과제를 한 후, 다시 $N + 1$일차에 첫 번째 과제를 하는 것을 반복하려고 한다.
단, 쉬는 날 없이 과제만 하게 되면 과로사를 할 수 있음으로, $M - 1$일 동안 과제를 하고 $M$일차에 휴식을 취하는 것을 반복할 것이다. 그러나 쉬는 날에 원래 해야 할 과제가 있다면, 그 과제를 다음날로 미루지 않고 아예 하지 않고 넘어갈 것이다.
예를 들어, $5$개의 과제가 있고 $4$일에 한 번씩 쉰다고 가정하면, $1$일 차에는 $1$번 과제를, $2$일 차에는 $2$번 과제를, $3$일 차에는 $3$번 과제를 수행한다. $4$일 차에는 $4$번 과제를 수행해야 하나, 휴식일이기 때문에 수행하지 않고 넘어간다. 대신, $5$일 차에는 $4$번 과제가 아닌 $5$번 과제를 수행해야 한다.
만족스러운 플랜을 짰다고 생각해 스스로 만족한 태호였으나, 막상 만들고 보니 과제를 언제 끝낼 수 있을지 궁금해졌다.
과제를 완료하는데 필요한 날의 정보와 휴식일의 정보가 주어질 때, 가장 먼저 끝나는 과제를 구해보자.
첫 줄에는 $N$과 $M$이 주어진다. ($2 \le N \le 20\ 000$, $2 \le M \le 500$)
두 번째 줄에 $X_1$, $X_2$, ..., $X_N$가 공백으로 구분되어 주어진다. ($1 \le X_i \le 125\ 000\ 000$)
태호가 가장 먼저 끝내는 과제의 번호를 출력한다.
5 7 4 2 2 3 5
3
태호는 다음과 같은 방법으로 과제를 진행한다.
8일차에 3번 과제를 모두 수행했으므로, 답은 $3$이 된다.
7 7 10 9 8 4 5 6 1
4
University > 연세대학교 > 2021 연세대학교 프로그래밍 경진대회 H번