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))

Объяснение:

Answer 2

Давайте разберемся. Чтобы помочь Мише выбраться из леса, давайте посчитаем общее количество шагов, которые он сделает до того, как окажется на границе леса.

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

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

Давайте выразим общее количество шагов в виде алгебраического выражения:

Общее количество шагов = (A + B + C + D) * общее количество оборотов + X

Где X - количество шагов, которое Миша сделает дополнительно, чтобы покинуть лес.

Так как Миша возвращается в центр квадрата после каждого цикла, то общее количество шагов для одного цикла равно A + B + C + D.

Чтобы Миша вышел из леса, общее количество шагов должно быть равно периметру квадрата (чтобы он достиг границы).

Периметр квадрата = 4 * сторона = 4 * 2K = 8K

Таким образом, общее количество шагов должно быть кратно периметру квадрата. Мы можем представить это как уравнение:

(A + B + C + D) * общее количество оборотов + X = 8K

Теперь найдем, сколько оборотов Миша сделает до того, как окажется на границе леса. Общее количество оборотов будет целым числом, которое удовлетворяет этому уравнению.

Таким образом, Миша сделает (8K - X) шагов перед тем, как окажется на границе леса. Важно отметить, что X - это количество шагов, которые он сделает дополнительно после последнего полного оборота, чтобы попасть на границу леса.

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

Это требует некоторых расчетов, и мне бы потребовалось точные значения A, B, C, D и K, чтобы дать окончательный ответ.