Встреча у фонтана Ограничение по времени: 0.5 секунды Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть…
Встреча у фонтана Ограничение по времени: 0.5 секунды Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть красивый фонтан, у которого Маша и Паша хотят сегодня встретиться. Известно, что Маша идёт до фонтана m минут, Паша — p минут. Выйти из домов они договорились одновременно, также друзья решили приходить к фонтану и, если там никого нет, идти обратно к дому, а затем снова разворачиваться, пока в итоге не случится встреча у фонтана. Помогите друзьям понять, смогут ли они встретиться в парке у фонтана, и если да, то сколько минут пройдёт с момента выхода из домов до их встречи. Формат входных данных Первая строка содержит целое число m (1⩽m⩽109) — время в минутах, которое требуется Маше, чтобы дойти от дома до фонтана. Вторая строка содержит целое число p (1⩽p⩽109) — время в минутах, которое требуется Паше, чтобы дойти от дома до фонтана. Формат выходных данных Выведите одно целое число — время, через которое Маша и Паша смогут встретиться у фонтана, если выйдут из домов одновременно, или −1, если этого никогда не случится. Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Система оценки Решения, правильно работающие, когда m и p не превосходят 103, будут оцениваться в 30 баллов. Решения, правильно работающие, когда ответ не превосходит 109, будут оцениваться в 60 баллов. Замечание Здесь и далее все временные отметки даются относительно начала движения, т. е. выхода из дома. В первом примере из условия Маша придёт к фонтану через 3 минуты, развернётся и пойдёт назад. Паша придёт к фонтану через 5 минут и отправится домой. Через 6 минут Маша доберётся до дома, вновь окажется у фонтана через 9 минут, опять не найдёт Пашу, развернётся и пойдёт домой. В следующий раз она будет у фонтана через 15 минут. Паша же дойдёт до дома через 10 минут и вернётся к фонтану через 15 минут, где он и встретится с Машей. Во втором примере Маша успеет дойти до фонтана и вернуться домой, пока Паша идёт до фонтана. Пока Паша возвращается домой, Маша опять проделывает путь до фонтана и обратно. Каждый раз, когда Паша оказывается у фонтана или у своего дома, Маша находится у своего дома, поэтому они не смогут встретиться.
Кратко суть задачи
- Маше нужно попасть в фонтан за время m, Паше — за время p.
- Они уходят одновременно, потом, если к fountain никого нет, возвращаются домой и снова отправляются к фонтану, пока не встретятся у фонтана.
- Встреча у фонтана возможна только тогда, когда оба будут у фонтана в одно и то же время.
Пошаговое решение
- Времена прибытия к фонтану у каждого
- Машa находится у фонтана в моменты времени t, удовлетворяющие t ≡ m (mod 2m). Это потому, что она достигает фонтана за m минут, затем возвращается домой за m минут, и так далее.
- Пашa находится у фонтана в моменты времени t, удовлетворяющие t ≡ p (mod 2p).
Задача сводится к нахождению наименьшего общего времени t, удовлетворяющего одновременно обе мод-коррекции: t ≡ m (mod 2m) t ≡ p (mod 2p)
- Условия существования решения Обозначим g = gcd(m, p). Пусть m = g·a, p = g·b, где gcd(a, b) = 1.
Из теории систем конгруэнций с не взаимно простыми модулями существование решения возможно только если a и b имеют одинаковую чётность. Но так как gcd(a, b) = 1, они либо оба нечетны, либо один чётный и другой нечётный. В итоге решение существует только если оба a и b нечётны, то есть: m/g и p/g — обе нечетные.
Если условие не выполняется, ответ = -1.
- Как найти минимальное время t (CRT) Пусть:
- n1 = 2m, a1 = m
- n2 = 2p, a2 = p
- d = gcd(n1, n2) = 2g
Если (a2 − a1) не делится на d, решения нет (но при выполнении условия выше это не происходит).
Пусть:
- n1' = n1/d = m/g = a
- n2' = n2/d = p/g = b
- c = (a2 − a1)/d = (p − m)/(2g)
Необходимо найти k такое, что n1'·k ≡ c (mod n2'). Так как gcd(n1', n2') = 1, можно взять обратную величину inv(n1' mod n2') и вычислить k ≡ c · inv(n1' mod n2') (mod n2').
Тогда минимальное неотрицательное решение: t = a1 + n1 · k
Примечание по вычислениям:
- Все арифметические промежуточные значения можно держать в 64-битах (макс примерно до 2·10^18).
- Чтобы корректно учесть возможную отрицательность c, вычисляйте k по модулю n2' и нормализуйте по положительным остаткам.
- Пример m = 3, p = 5
- g = gcd(3,5) = 1
- m/g = 3 (нечное), p/g = 5 (нечное) → решение существует
- n1 = 6, a1 = 3; n2 = 10, a2 = 5; d = 2
- n1' = 3, n2' = 5, c = (5 − 3)/2 = 1
- inv(3 mod 5) = 2 (п because 3·2 ≡ 1 mod 5)
- k ≡ 1 · 2 ≡ 2 (mod 5)
- t = a1 + n1·k = 3 + 6·2 = 15
Ответ: 15
- Ещё пример m = 2, p = 4
- g = gcd(2,4) = 2
- m/g = 1, p/g = 2 → один из них чётный, значит решение не существует
- Ответ: -1
- Алгоритм (для реализации)
- Ввести m, p (тип long long).
- g = gcd(m, p).
- Если (m/g) и (p/g) не оба нечетные, вернуть -1.
- d = 2*g
- n1 = 2*m, a1 = m
- n2 = 2*p, a2 = p
- n1' = n1 / d, n2' = n2 / d, c = (a2 - a1) / d
- inv = модульный обратный коэффициент к n1' по mod n2' (находитc через расширенный НОД; так как gcd(n1', n2') = 1, обратный есть)
- k = ((c mod n2') * inv) mod n2' (обеспечиваем положительный остаток)
- t = a1 + n1 * k
- вернуть t
- Что это даёт
- Если m/g и p/g оба нечетны, встреча произойдёт, и время t можно найти указанным способом.
- Время t может быть очень большим, но не превосходит порядка 2·m·p, что помещается в 64-битное целое.
Итого
- Условия существования: m/g и p/g должны быть обе нечётные.
- Время встречи: наименьшее решение системы t ≡ m (mod 2m), t ≡ p (mod 2p) вычисляется через CRT в линейном времени (логарифм по числу разрядов).
Если хотите, могу привести готовую короткую реализацию на C++ (с использованием расширенного НОД для modular inverse) или привести пошаговый разбор под конкретные числа.
