시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 149 | 38 | 32 | 35.556% |
N개의 손가락을 가진 세빈이는 한 손만으로 모든 곡을 연주할 수 있는 최고의 피아니스트다.
세빈이의 두 인접한 손가락 사이의 거리는 K로 일정하다. 고로 i번째 손가락과 첫 번째 손가락 사이의 거리를 Xi라고 한다면, Xi = (i-1)K가 성립한다(1 ≤ i ≤ N).
세빈이는 M개의 음으로 이루어진 곡을 연주하려 한다. 이때 각각의 음을 어떤 손가락으로 연주하는지에 따라 곡을 연주하는 것이 쉬워질 수도, 어려워질 수도 있다.
i번째 음의 음높이를 Pi라 하고, 이 음을 Fi번째 손가락으로 연주한다 하자. i번째 음과 이와 인접한 (i+1)번째 음을 연주할 때의 난이도는 |(Pi+1 - Pi) - (XFi+1 - XFi)|다.
곡의 난이도는 인접한 두 음을 연주할 때의 난이도의 최댓값으로 정의한다. 각각의 음을 어떤 손가락으로 연주할지 결정하여 곡의 난이도를 최소화하는 프로그램을 작성하시오.
첫 번째 줄에 세빈이의 손가락의 수와 곡을 이루는 음의 수를 나타내는 두 자연수 N과 M, 두 인접한 손가락 사이의 거리를 나타내는 자연수 K가 사이에 공백을 두고 주어진다.
두번째 줄에는 M개의 정수 P1, ···, PM이 사이에 공백을 두고 주어진다.
첫 번째 줄에 곡의 난이도의 최솟값을 출력한다.
모든 입력 데이터는 다음 조건을 만족한다.
5 4 3 7 2 9 3
1
F1 = 3, F2 = 1, F3 = 3, F4 = 1.
High School > 경기과학고등학교 > 나는코더다 2019 송년대회 G번