Question

Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из N ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков. Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее X, а длинный — на произвольное число, не большее Y (X < Y). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков.Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех N ступенек.Входные данныеВ первой строке входных данных записано целое число X — максимальная длина короткого прыжка.Во второй строке записано целое число Y (1 ≤ X < Y < 1018) — максимальная длина длинного прыжка.В третьей строке записано целое число N (1 < N < 1018) — количество ступенек в спуске.Выходные данныеВ единственной строке выведите целое число — минимальное число прыжков, необходимое Марио для спуска.​

Answer 1

Ответ:  

X = int(input())

Y = int(input())

N = int(input())

if (N % (X + Y)) == 0:

  print(int((N / (X + Y))*2))

else:

  if (N % (X + Y)) <= Y:

      print(int(((N//(X + Y))*2)+1))

  else:

      print(int(((N//(X + Y))*2)+2))

Объяснение:

Answer 2

Ответ:

X = int(input())

Y = int(input())

N = int(input())

if (N % (X + Y)) == 0:

  print(int((N / (X + Y))*2))

else:

  if (N % (X + Y)) <= Y:

      print(int(((N//(X + Y))*2)+1))

  else:

      print(int(((N//(X + Y))*2)+2))

Объяснение:

ПИТОН

Answer 3

Данная задача является классической задачей динамического программирования, которая может быть решена с использованием рекурсии с запоминанием (memoization).

Введем функцию minJumps(n), которая будет возвращать минимальное количество прыжков, необходимое для преодоления n ступенек.

Сначала проверим базовые случаи:

• Если n равно 0, то нет необходимости делать ни одного прыжка, поэтому возвращаем 0.
• Если n равно 1, то можем сделать только короткий прыжок, поэтому возвращаем 1.

Затем рассмотрим общий случай:

• Если n больше 1, то есть две возможности:
  1. Марио делает короткий прыжок с длиной X и остается n-X ступенек. Тогда общее количество прыжков равно 1 + minJumps(n-X).
  2. Марио делает длинный прыжок с длиной Y и остается n-Y ступенек. Тогда общее количество прыжков равно 1 + minJumps(n-Y).

Итак, общая формула будет выглядеть следующим образом:

minJumps(n) = 1 + min(minJumps(n-X), minJumps(n-Y))

Также необходимо учесть ограничение, что два длинных прыжка подряд сделать нельзя. Это означает, что если n <= Y, то максимальное количество прыжков будет равно 1 (делаем короткий прыжок).

Приведем решение на языке Python:

pythonCopy code
memo = {}

def minJumps(n, X, Y):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n <= Y:
        return 1
    if n in memo:
        return memo[n]
    jumps = 1 + min(minJumps(n-X, X, Y), minJumps(n-Y, X, Y))
    memo[n] = jumps
    return jumps

X = int(input())
Y = int(input())
N = int(input())

result = minJumps(N, X, Y)
print(result)

При использовании данного кода входные данные должны быть введены пользователем, и результат будет выведен на экран.