Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть красивый фонтан, у которого Маша и Паша хотят сегодня встретиться. Известно, что Маша идёт до фонтана m
минут, Паша —
p
минут.
Выйти из домов они договорились одновременно, также друзья решили приходить к фонтану и, если там никого нет, идти обратно к дому, а затем снова разворачиваться, пока в итоге не случится встреча у фонтана.
Помогите друзьям понять, смогут ли они встретиться в парке у фонтана, и если да, то сколько минут пройдёт с момента выхода из домов до их встречи. написать решение в языке программирования Python
Ниже приводится подробное решение с кратким объяснением и готовым кодом на Python.
Идея решения
- Время прибытия каждой из них к фонтану чередуется: Маша посещает фонтан на временах m, 3m, 5m, ...; Паша — на p, 3p, 5p, ...
- Встреча у фонтана возможна только тогда, когда оба окажутся у фонтана в одно и то же время: t = m(2k+1) = p(2l+1).
- Пусть g = gcd(m, p). Запишем m = g*m1, p = g*p1, где gcd(m1, p1) = 1.
Уравнение становится m1(2k+1) = p1(2l+1). Так как m1 и p1 взаимно просты, чтобы левая и правая части были равны, обе множители m1 и p1 должны быть нечетными. Следовательно, чтобы встреча была возможна, должны выполняться условия:
- m/g и p/g оба нечетные (то есть v2(m) = v2(p)).
- Если условие выполняется, минимальное время встречи равно НОК(m, p) = m * p / gcd(m, p).
- Если условие не выполняется, встреча невозможна.
Пример: m = 3, p = 5 → gcd = 1, m/g = 3, p/g = 5 оба нечетные → встреча через t = lcm(3,5) = 15 минут.
Пример: m = 2, p = 4 → gcd = 2, m/g = 1 (нечетное), p/g = 2 (четное) → встреча невозможна.
Код на Python
- Вход: два целых числа m и p (минуты до фонтана от каждого дома).
- Выход: минимальное время встречи в минутах, или -1 если встреча невозможна.
```python
import sys
import math
def main():
data = sys.stdin.read().strip().split()
if not data:
return
m, p = map(int, data[:2])
g = math.gcd(m, p)
m1 = m // g
p1 = p // g
# встреча возможна только если m1 и p1 оба нечетные
if (m1 & 1) and (p1 & 1):
t = m * p // g # lcm(m, p)
print(t)
else:
print(-1)
if __name__ == "__main__":
main()
```
Как тестировать
- Ввод: 3 5
Вывод: 15
- Ввод: 2 4
Вывод: -1
Если нужна форматированная версия вывода (например, сначала “YES” и потом время), можно легко адаптировать код: заменить вывод на печать "YES" и t, или "NO" вместо -1.
