Python

Лес - задача по информатике

Миша заблудился в лесу и пытается выйти из него. Он проходит A шагов на север, затем B шагов на восток, затем C шагов на юг, D шагов на запад, после чего повторяет свои действия (снова A шагов на север, B шагов на восток, C шагов на юг, D шагов на запад и т.д.).

Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K шагов в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K шагов.

Определите, сколько шагов Миша сделает, прежде чем выйдет из леса (впервые окажется на границе леса).

Входные данные
Первые четыре строки входных данных содержат по одному целому положительному числу A, B, C, D — количество шагов, которое Миша делает на север, восток, юг, запад. Пятая строка входных данных содержит целое число K — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Все входные числа не превосходят 109.

Выходные данные
Программа должна вывести одно целое число — количество шагов, которое Миша сделает до выхода из леса. Гарантируется, что входные данные таковы, что Миша когда-нибудь выйдет из леса.

Обратите внимание, что значение ответа может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Система оценки
Решения, правильно работающие, когда входные числа не превосходят 100, будут оцениваться в 32 балла.

Пример
Ввод:
1
1
2
3
3
Вывод:
13

Пояснение:
На рисунке изображён пример из условия. Миша делает 1 шаг на север (вверх), 1 шаг на восток (вправо), 2 шага на юг (вниз), 3 шага на запад (влево). От начального расположения Миши до стороны квадрата — 3 шага. Первоначальное расположение Миши и точка выхода из леса обозначены синими кругами. Путь Миши обозначен жёлтой линией. Миша пройдёт 13 шагов, прежде чем впервые окажется на границе леса.
Азамат Азамат
Азамат Азамат
90
Еще вариант.
Не уверен, что чево-нибудь не упустил, но по-моему так:
https://pastebin.com/AwrgPGL9

----------
from time import time
a = 1
b = 1
c = 2
d = 3
k = 3
#----------------------------------------
##stt=time()
dx = b-d # смещение x за цикл
dy = a-c # смещение y за цикл
rx = max(b,abs(b-d)) # радиус цикла x
ry = max(a,abs(a-c)) # радиус цикла y
stpc = a+b+c+d # шагов за цикл
##print(dx, dy, rx, ry, stpc)

n_cycl = min((k-rx)//abs(dx), (k-ry)//abs(dy))
if n_cycl < 0:
~~~~n_cycl = 0
##print(n_cycl)

kyp = k - dy*n_cycl
kym = k + dy*n_cycl
kxp = k - dx*n_cycl
kxm = k + dx*n_cycl
x, y = 0, 0
stp = 0
while 1:
~~~~stp += a
~~~~y += a
~~~~if y >= kyp:
~~~~~~~~stp -= y - kyp
~~~~~~~~break
~~~~
~~~~stp += b
~~~~x += b
~~~~if x >= kxp:
~~~~~~~~stp -= x - kxp
~~~~~~~~break

~~~~stp += c
~~~~y -= c
~~~~if y <= -kym:
~~~~~~~~stp -= -y - kym
~~~~~~~~break

~~~~stp += d
~~~~x -= d
~~~~if x <= -kxm:
~~~~~~~~stp -= -x - kxm
~~~~~~~~break
print(n_cycl*stpc + stp)
##print(time()-stt)
Сережа Попов
Сережа Попов
21 729
Лучший ответ
Для данного конкректного случая. Хотя в олимпиадных задачах наверняка не всё так просто...
Сергей Гриб
Сергей Гриб
75 240
Евгений Стрелов на каком языке ?
Andrey Gremilov где инпут

Похожие вопросы