|
Мышка с колесиком
(Время: 0,5 сек. Память: 16 Мб Сложность: 54%)
Пользователь просматривает таблицу в Internet Explorer и пользуется для прокрутки изображения колесиком на мышке. При этом все изображение сдвигается вверх или вниз на T пикселей. Пользователю очень не нравится, когда курсор мыши оказывается на горизонтальных линиях, разделяющих строки таблицы. Поэтому он хочет выбрать такое положение для курсора мыши на экране, чтобы в процессе прокрутки до конца таблицы курсор как можно меньшее число раз пересекался с линиями таблицы.
При этом если в каком-то положении курсор оказывается на двух линиях таблицы, то это считается за два пересечения курсора с линиями таблицы. Если какую-то линию курсор мыши пересекает в двух положениях (то есть, например, высота курсора 10 пикселей, а при прокрутке таблица сдвигается на 7 пикселей, тогда курсор мыши может оказываться на одной линии в двух состояниях прокрутки), то это также считается за два пересечения.
Экран монитора имеет разрешение по вертикали U пикселей. Координаты введены так, что самые верхние точки экрана имеют координату 0, а нижние — координату U–1. Курсор мыши имеет высоту H пикселей. Расположением курсора считается самая верхняя точка курсора. Таким образом, если мы говорим, что он расположен, например, в точке с координатами 0 на экране, то его изображение расположено в точках с координатами от 0 до H–1. Курсор мыши всегда целиком помещается на экране, то есть допустимыми координатами для его расположения являются координаты от 0 до U–H. Таблица, которую просматривает пользователь, имеет высоту L пикселей и состоит из N–1 строки, и, следовательно, в ней N горизонтальных линий, которые имеют координаты X1, X2, …, XN. При этом 0 = X1 < X2 < X3 < … < XN = L–1.
В начальный момент времени таблица расположена так, что линия, имеющая координату 0 в таблице отображается в 0-й строке пикселей монитора. Далее при прокрутке таблица каждый раз сдвигается на T пикселей (то есть в 0-й строке монитора оказывается строка пикселей, имеющая в таблице координату T, координату 2T и т.д.). Так происходит до тех пор, пока на экране не окажется нижняя линия таблицы (которая имеет координату XN). После этого дальнейшая прокрутка не происходит (если изначально XN < U, то прокрутка вообще не происходит).
Входные данные
Во входном файле INPUT.TXT задано сначала разрешение монитора по вертикали U, затем высота курсора мыши H, затем шаг прокрутки T. Далее задана высота таблицы L. Далее задано количество разделительных линий в таблице N, и координаты X1, X2,…,XN, где расположены эти линии относительно начала таблицы. Ограничения: 10 ≤ U ≤ 512, 1 ≤ H ≤ U, 1 ≤ T ≤ U, 2 ≤ N ≤ 200000, 0 = X1 < X2 < X3 < … < XN = L–1 ≤ 109.
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести наименьшее возможное количество пересечений курсора мыши с линиями таблицы.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10 3 10 10
4
0 1 6 9
| 0 |
| 2 | 10 6 2 21
11
0 2 4 6 8 10 12 14 16 18 20
| 21 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
