Задача №114889. Ландшафтный дизайн
Марио решил заняться ландшафтным дизайном. Сейчас его сад можно представить как n вертикальных столбиков, i -й из которых начинается на y координате a i , и уходит бесконечно вниз. За одну операцию Марио может изменить высоту любого столбика на 1 (обратите внимание, что высоты могут становиться отрицательными). Марио хочет изменить высоты столбиков с a i на b i так, чтобы для любого 1 ≤ i ≤ n - 2 выполнялось b i = b i + 2 , а любые два соседних столбика отличались по высоте ровно на k .
Помогите Марио выяснить, какое минимальное количество операций ему придется сделать.
В первой строке даны два целых числа n и k — количество столбиков, и высота на которую должны отличаться два соседних столбика ( 2 ≤ n ≤ 10 5 , 0 ≤ k ≤ 10 9 ). В следующей строке даны n целых чисел a i — исходные высоты столбиков ( - 10 9 ≤ a i ≤ 10 9 ).
В единственной строке выведите минимальное число операций, которое придется сделать Марио, чтобы получить желаемые высоты столбиков.
Эта задача состоит из трех подзадач. Для подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Номера необходимых подзадач также указаны в таблице.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
| 1 | 31 | n ≤ 1 000 , k ≤ 1 000 , | a i | ≤ 1 000 | — |
| 2 | 53 | n ≤ 10 5 , k ≤ 1 000 , | a i | ≤ 1 000 | 1 |
| 3 | 16 | n ≤ 10 5 , k ≤ 10 9 , | a i | ≤ 10 9 | 1, 2 |
В первом тесте Марио может, например, получить следующую последовательность b i : 2 , 1 , 2 , 1 , 2 .
5 1 1 2 3 -1 2
5