Question

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

Answer 1

import sys

A = int(input())

B = int(input())

C = int(input())

D = int(input())

K = int(input())

def check(x, y):

   if abs(x) > K or abs(y) > K:

       return 0

   y += A

   if y >= K:

       return A - (y - K)

   x += B

   if x >= K:

       return A + B - (x - K)

   y -= C

   if y <= -K:

       return A + B + C - (-y - K)

   x -= D

   if x <= -K:

       return A + B + C + D - (-x - K)

   return -1

if check(0, 0) != -1:

   print(check(0, 0))

   sys.exit(0)

x = B - D

y = A - C

left = 0

right = 10 ** 9

while right - left > 1:

   mid = (left + right) // 2

   if check(x * mid, y * mid) == -1:

       left = mid

   else:

       right = mid

print(right * (A + B + C + D) + check(x * right, y * right))

Объяснение: