Родители Лизы подключили пакет, содержащий N телевизионных каналов, пронумерованных числами от 1 до N
Родители Лизы подключили пакет, содержащий N
телевизионных каналов, пронумерованных числами от 1
до N
.
Переключать каналы можно с помощью двух кнопок на пульте: «+
» и «–
».
Короткое нажатие на кнопку «+
» приведёт к переключению на следующий канал, если номер текущего канала меньше N
; если же номер текущего канала равен N
, то телевизор продолжит показывать этот канал. Если кнопку «+
» нажать и удерживать некоторое время, произойдёт переход на K
каналов вперёд при условии, что номер текущего канала не превосходит N−K
. В противном случае произойдёт переход на канал N
.
Аналогично, короткое нажатие на кнопку «−
» приведёт к переключению на предыдущий канал, если номер текущего канала больше 1
; если же номер текущего канала равен 1
, телевизор продолжит показывать этот канал. Если кнопку «−
» нажать и удерживать некоторое время, то произойдёт переход на K
каналов назад при условии, что номер текущего канала превышает K
. В противном случае произойдёт переход на канал 1
.
Лиза включила телевизор и обнаружила, что он показывает канал P
. Лиза знает, что очень скоро по каналу с номером U
начнётся интересная передача. Определите, какое минимальное количество нажатий на кнопки пульта потребуется сделать Лизе, чтобы переключиться на канал U
.
Формат входных данных
В первой строке содержится целое число N
(3≤N≤109)
—
количество телевизионных каналов.
Во второй строке содержится целое число K
(2≤K<N)
—
количество каналов, на которое осуществится переход назад или вперёд при удерживании соответствующей кнопки переключения.
В третьей строке содержится целое число P
(1≤P≤N)
—
номер канала, который показывает телевизор.
В четвёртой строке содержится целое число U
(1≤U≤N)
—
номер канала, на который желает переключиться Лиза.
Гарантируется, что P≠U
.
Формат выходных данных
Выведите одно целое неотрицательное число —
минимальное количество нажатий на кнопки пульта, которое необходимо для переключения с канала P
на канал U
.
Система оценки
Решения, правильно работающие при P<U
, N≤100
, будут оцениваться в 24
балла.
Решения, правильно работающие при N≤100
, будут оцениваться в 48
баллов.
Замечание
В первом примере Лизе следует сначала выполнить одно короткое нажатие на кнопку «+
» и переключиться с канала 3 на канал 4 , а затем трижды осуществить переход вперёд на 5 каналов: сначала переключиться с 4 на 9 , затем с 9
на 14 и, наконец, с 14 на 19 канал.
Во втором примере Лиза может сначала переключиться коротким нажатием на кнопку «− » на канал 2 , после чего выполнить три перехода вперёд на 5
каналов: с канала 2 на канал 7 , затем на канал 12 и, наконец, на канал 17 .
В третьем примере Лиза дважды выполнит короткое нажатие кнопки «−
».
В четвёртом примере Лизе нужно сначала перейти назад, на канал 1 , после чего трижды выполнить переход вперёд, последовательно на каналы 6 , 11 , 16 .
Дельный пример на тему, что можно сначала сделать шаг назад и "оттолкнуться от стенки". Причём, таких шагов может быть несколько, из общих соображений - до половины квадрата k. Попробуй вот так:
def paths(n, k, p, u):
d = abs(p - u)
t = divmod(d, k)
j = (p - 2) % k + 1 if p > u < t[1] else (n - p) % k if p < u > n - k + t[1] else k
return (sum(t), 1 + j + int.__sub__(*t)) + tuple(
map(((p + k - 2) // k).__add__, paths(n, k, 1, u)) if u > p and 1 < p < k * k // 2
else map(((n - p + k - 1) // k).__add__, paths(n, k, n, u)) if u < p and n > p > n - k * k // 2
else ()
)
n, k, p, u = map(int, map(input, ('',) * 4))
print(min(paths(n, k, p, u))) Здесь рассматриваются до 4-х путей одновременно и из них выбирается минимум. Пример:
100
20
67
37 Здесь надо сделать 2 длинных шага назад, упереться в 100, затем 3-мя длинными шагами спуститься к 40, и 3-мя маленькими - к 37, итого 8. По прямому пути было бы 11, по пути с возвратом от следующей "станции" - 12. В обратную сторону этот подход тоже работает.
Алгоритм немножко рекурсивный, но глубина рекурсии не превышает 2.