문제
승호는 각종 타임어택 대회의 5관왕이다.
승호가 보유한 타이틀은 다음과 같으며, 모두 1위를 했다:
짜장면 빨리 먹기, 컴퓨터 빨리 조립하기, 큐브 빨리 맞추기, 카드 빨리 쌓기, 그리고 여자친구 빨리 만들기(특히 이 대회에서 우승할 때는 신기록을 갈아치웠다고 한다.)
오늘 또 다른 타임어택 대회가 있다. 이 대회의 이름은 수열 빨리 바꾸기인데, 규칙은 다음과 같다. n개의 수열의 원소가 차례대로 주어진다.
승호와 참가자들은 위치에 상관없이 한 가지 원소를 다른 값으로 바꾸는데 1초의 시간이 걸린다.
참가자들의 목적은 최대한 빨리 공차가 k인 등차수열을 만드는 것이다.
공차가 k인 등차수열이란, 모든 인접한 두 원소를 고려할 때, 오른쪽 원소-왼쪽 원소 = k를 만족하는 수열이다.
예를 들어 처음에 주어진 수열이 [1, 2, 5]이고, k = 2라고 하자.
첫번째 수와 세번째 수를 0, 4로 바꾸는데 2초가 걸리며, [0, 2, 4]는 공차가 2인 등차수열이 된다.
그러나 이렇게 하지 않고, 두 번째 수를 3으로 바꾸면 1초밖에 걸리지 않는다.
이렇게 해서 만들어진 [1, 3, 5]도 공차가 2인 등차수열이다.
0초만에 등차수열을 만드는 방법이 없으므로, 1초 걸려서 공차가 2인 등차수열을 만든 경우가 우승이다.
승호의 6관왕 타이틀을 위해, 공차 k와 수열의 원소들이 주어졌을 때, 우승하는데 걸리는 가장 적게 걸리는 시간을 출력하는 프로그램을 작성하라.
입력
첫째 줄에 수열의 원소의 개수인 n과 공차 k가 공백을 사이에 두고 주어진다.
둘째 줄에 n개의 수열의 원소 ai가 순서대로 공백을 사이에 두고 주어진다.
[제약 조건]
모든 부분문제에서 2≤n≤100,000, -100,000 ≤ k ≤ 100,000을 만족한다.
모든 부분문제에서 -109≤ai≤10<9를 만족한다.모든 입력값은 정수이다.
출력
주어진 수열의 원소들로 대회를 우승하는데 걸리는 최소시간을 초 단위로 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 9점 | k=0을 만족한다. |
| #2 | 16점 | n≤1,000을 만족한다. |
| #3 | 23점 | -100,000≤ai≤100,000를 만족하며, -3,000,000≤n×k≤3,000,000(3백만)을 만족한다. |
| #4 | 52점 | 주어진 제약조건 외에 아무 제약조건이 없다. |
예제
6 2
1 2 5 7 9 85
2
로그인해야 코드를 작성할 수 있어요.