На кольцевом маршруте автобуса N остановок. Это значит, что через N остановок автобус возвращается в начало маршрута. Петя сел в автобус у дома и тут же заснул. Через X остановок…
На кольцевом маршруте автобуса N остановок. Это значит, что через N остановок автобус возвращается в начало маршрута. Петя сел в автобус у дома и тут же заснул. Через X остановок он проснулся. Чтобы не пересаживаться на автобус, идущий обратно, он решил остаться в автобусе, доехать до своей остановки и выйти (но не делать больше лишних кругов). Даны числа N и X. Какое минимальное количество остановок Пете нужно проехать, чтобы вернуться домой? Ввод Вывод 9 21 6 9 18 0 Примечание: если Петя проехал 21 остановку (а на маршруте всего 9 остановок), это значит, что он сделал 2 полных круга и проехал ещё 3 остановки. Чтобы вернуться домой, ему нужно проехать ещё 6 остановок. А если он проехал 18 остановок (на том же маршруте с 9-ю остановками), это значит, что он проехал ровно 2 круга и может выйти прямо сейчас.
Решение задачи понятного типа: минимальное количество остановок, которое Пете нужно проехать дальше по кольцевому маршруту, чтобы вернуться домой.
Описание и вывод формулы
- Пусть N – число остановок в круге, X – число остановок, которые Петр проехал после того, как уснул.
- После X остановок автобус находится на остановке X mod N (относительно его дома, который можно считать позицией 0).
- Чтобы вернуться домой, нужно проехать еще r остановок так, чтобы (X + r) mod N = 0.
- Это даёт общую формулу: r = (N − (X mod N)) mod N.
- если X mod N = 0, то r = 0 (он уже на своей остановке);
- иначе r = N − (X mod N).
Пояснение простыми словами
- Представьте, что бегунок идёт по кругу из N остановок. После X пройденных остановок вы находитесь на позиции X mod N. Чтобы вернуться к позиции 0 (дом), нужно ехать дальше на N − (X mod N) остановок, но если остаток 0, так и быть: 0 дополнительных остановок.
Примеры на основе данных
- Пример 1: N = 9, X = 21
- X mod N = 21 mod 9 = 3
- r = 9 − 3 = 6
- Ответ: 6
- Пример 2: N = 9, X = 18
- X mod N = 18 mod 9 = 0
- r = 0
- Ответ: 0
Дополнительные заметки
- Можно вычислять напрямую как r = ((N − (X % N)) % N).
- В большинстве языков программирования можно использовать как r = (-X) % N (это эквивалентно той же формуле для положительного N).
- Алгоритм работает за O(1) времени и O(1) памяти.
Если нужно, могу привести компактный пример кода на Python или любом другом языке.
