Минимальное число ударов для убийства Змея Горыныча по заданным правилам

Ответ выходит не верный:

для змея с одной головой и одним хвостом ваша программа обещает управиться за один удар. Интересно, как?

Если у змея три головы и три хвоста, ваша программа обещает управиться за три удара. Как это возможно, если учесть что за один удар можно отрезать не более двух "отростков"? Снова в конце комбоудар по хвосту и голове?

Результат: 3 головы, 3 хвоста - 9 ударов, 1 голова, 1 хвост - 3 удара.

Автономный скрипт, который можно поместить в файл и запустить:

import os
from collections import deque

def min_strikes(num_heads, num_tails, max_limit = 200):
 # Вычисляем разумные верхние границы для количества голов и хвостов
 # Это нужно, чтобы BFS не ушёл в бесконечный рост хвостов
 max_heads = max(num_heads + max_limit, 200)
 max_tails = max(num_tails + max_limit, 200)

 # Создаём очередь для BFS
 # Каждый элемент очереди: (текущее число голов, текущее число хвостов, количество ударов)
 queue = deque([(num_heads, num_tails, 0)])

 # Множество visited хранит уже посещённые состояния (чтобы не повторять)
 visited = {(num_heads, num_tails)}

 while queue:
  # Берём текущее состояние
  heads, tails, strikes = queue.popleft()

  # --- Действие 1: отрубить две головы ---
  # Если голов ≥ 2, можно нанести удар по двум
  if heads >= 2:
   nh, nt = heads - 2, tails  # новое состояние после удара
   if nh == 0 and nt == 0:  # если все головы и хвосты уничтожены
    return strikes + 1  # возвращаем общее количество ударов
   # Добавляем новое состояние в очередь, если ещё не посещено и не превышает границы
   if (nh, nt) not in visited and nh <= max_heads and nt <= max_tails:
    visited.add((nh, nt))
    queue.append((nh, nt, strikes + 1))

  # --- Действие 2: отрубить один хвост ---
  # Если хвостов ≥ 1, удар увеличивает количество хвостов на 1 (выросший хвост)
  if tails >= 1:
   nh, nt = heads, tails + 1
   if nh == 0 and nt == 0:  # проверка на смерть Змея
    return strikes + 1
   if (nh, nt) not in visited and nh <= max_heads and nt <= max_tails:
    visited.add((nh, nt))
    queue.append((nh, nt, strikes + 1))

  # --- Действие 3: отрубить два хвоста ---
  # Если хвостов ≥ 2, из них вырастает одна голова, хвосты уменьшаются на 2
  if tails >= 2:
   nh, nt = heads + 1, tails - 2
   if nh == 0 and nt == 0:  # проверка на смерть Змея
    return strikes + 1
   if (nh, nt) not in visited and nh <= max_heads and nt <= max_tails:
    visited.add((nh, nt))
    queue.append((nh, nt, strikes + 1))

 # Если очередь закончилась и состояние "0 голов и 0 хвостов" не достигнуто
 return None  # Змея уничтожить невозможно в пределах поиска

# --- Чтение входных данных ---
try:
 start_heads = int(input("Введите число голов: "))
 start_tails = int(input("Введите число хвостов: "))
 # Проверка на натуральные числа (≥1)
 if start_heads < 1 or start_tails < 1:
  raise ValueError
except Exception:
 print("Ошибка: нужно вводить только натуральные числа (≥1)!")
 os.system("pause")
 exit(1)

# --- Вызов функции поиска минимального количества ударов ---
result = min_strikes(start_heads, start_tails)

# --- Вывод результата ---
if result is None:
 print("Решение не найдено при заданных параметрах!")
else:
 print(f"Минимальное количество ударов: {result}")

# Задержка окна, чтобы пользователь успел увидеть результат
os.system("pause")

По идее, тут не нужен цикл, задача скорее на математику, надо просто рассмотреть варианты. Нам нужна функция количества ударов F(H, T), где H - количество голов, T - количество хвостов

F(2N+1, 0) = бесконечность

F(2N, 4K) = N+3K (из 4К хвостов делаем 2К голов за 2К ударов, потом N ударов по "старым" головам и K ударов по "новым")

F(2N, 4K+3) = 1 + F(2N, 4*(K+1)) (первым ударом по хвосту приводим задачу к предыдущему пункту, только вместо К будет К+1)

F(2N, 4K+2) = 1 + F(2N, 4K + 3) (аналогично)

F(2N, 4K+1) = 1 + F(2N, 4K + 2) (тоже самое)

F(2N+1, 4K+2) = N + 3K + 2 (из 4К+2 хвостов делаем 2К+1 голов за 2К+1 ударов, потом N ударов по "старым" головам и K ударов по "новым" и один удар по "смешанной" паре голов)

F(2N+1, 4K+1) = 1 + F(2N+1, 4K+2)

F(2N+1, 4K) = 1 + F(2N+1, 4K+1)

F(2N+1, 4K+3) = 1 + F(2N+1, 4*(K+1))

пример:

F(3, 3) = 1 + F(3, 4) = 2 + F(3, 5) = 3 + F(3, 6) =
 = 3 + F(2*1+1, 4*1+2) = 3 + 1 + 3*1 + 2 = 9

Аналитическое решение задачи.

Очевидно, что для того, чтобы приговорить Горыныча, его необходимо оставить без хвостов и с чётным количеством голов. Каждые четыре хвоста двумя ударами превращаются в две головы, которые отрубаются третьим ударом. То есть решение нашей задачи будет зависеть от остатка от деления количества хвостов Горыныча на 4, а также от остатка от деления количества его голов на 2. При этом нам могут понадобиться такие операции:

• Добавить одну голову, убрав один хвост:

  1. -1 хвост +2 хвоста
  2. -2 хвоста +1 голова

  (2 удара)

• Добавить две головы, убрав один хвост:

  1. -1 хвост +2 хвоста
  2. -1 хвост +2 хвоста (итого 3 хвоста)
  3. -1 хвост +2 хвоста (итого 4 хвоста)
  4. -2 хвоста +1 голова
  5. -2 хвоста +1 голова

  (5 ударов)

• Добавить одну голову, убрав два хвоста:

  1. -2 хвоста +1 голова

  (1 удар)

• Добавить две головы, убрав два хвоста:

  1. -1 хвост +2 хвоста (итого 3 хвоста)
  2. -1 хвост +2 хвоста (итого 4 хвоста)
  3. -2 хвоста +1 голова
  4. -2 хвоста +1 голова

  (4 удара)

Также стоит заметить, что бесхвостый Горыныч с нечётным количеством голов в рамках законов нашей вселенной является бессмертным, аки сам Кощей, ибо снабдить его дополнительной чётной головой у нас нет ни малейшей возможности.

Рассмотрим все 8 возможных вариантов:

• Количество голов чётное:

  • Количество хвостов делится на 4 нацело (самый простой случай):

    1. Из каждых четырёх хвостов за два удара получаем две головы, ещё за один удар рубим эти две головы, итого 3 удара на каждые 4 хвоста;
    2. Рубим оставшиеся головы, по одному удару на каждые 2 головы.

    strikes = tails//4*3 + heads//2

  • Остаток от деления количества хвостов на 4 равен 1:

    1. Рубим по четыре хвоста и две головы (3 удара на каждые 4 хвоста);
    2. Делаем из одного хвоста две головы (5 ударов) и рубим их (ещё 1 удар);
    3. Рубим оставшиеся головы (1 удар на каждые 2 головы).

    strikes = tails//4*3 + 6 + heads//2

  • Остаток от деления количества хвостов на 4 равен 2:

    1. Рубим по четыре хвоста и две головы (3 удара на каждые 4 хвоста);
    2. Делаем из двух хвостов две головы (4 удара) и рубим их (ещё 1 удар);
    3. Рубим оставшиеся головы (1 удар на каждые 2 головы).

    strikes = tails//4*3 + 5 + heads//2

  • Остаток от деления количества хвостов на 4 равен 3:

    1. Рубим по четыре хвоста и две головы (3 удара на каждые 4 хвоста);
    2. Рубим ещё два хвоста, количество голов увеличивается на единицу и становится нечётным;
    3. Делаем из оставшегося хвоста ещё одну голову (2 удара), количество голов увеличилось ещё на единицу и стало опять чётным;
    4. Рубим две последние головы;
    5. Рубим оставшиеся головы (1 удар на каждые 2 головы).

    strikes = tails//4*3 + 4 + heads//2

• Количество голов нечётное:

  При составлении формул для следующих четырёх случаев при упрощении уравнений будем иметь ввиду, что поскольку исходное количество голов у нашего Горыныча нечётное,

  (heads + 1)//2 = heads//2 + 1
  

  • Количество хвостов делится на 4 нацело:

    1. Рубим по четыре хвоста и две головы, кроме последних четырёх хвостов (3 удара на каждые 4 хвоста);
    2. Рубим два хвоста (количество голов увеличилось на единицу и стало чётным, осталось два хвоста);
    3. Делаем из оставшихся двух хвостов ещё две головы (4 удара) и рубим их (ещё 1 удар);
    4. Рубим оставшиеся головы.

    strikes = (tails//4 - 1)*3 + 6 + (heads + 1)//2

    Упрощаем:

    strikes = tails//4*3 - 3 + 6 + heads//2 + 1 = (tails//4)*3 + 4 + heads//2

  • Остаток от деления количества хвостов на 4 равен 1:

    1. Рубим по четыре хвоста и две головы (3 удара на каждые 4 хвоста);
    2. Делаем из оставшегося хвоста ещё одну голову (2 удара), количество голов увеличивается на единицу и становится чётным;
    3. Рубим оставшиеся головы.

    strikes = tails//4*3 + 2 + (heads + 1)//2 = tails//4*3 + 3 + heads//2

  • Остаток от деления количества хвостов на 4 равен 2:

    1. Рубим по четыре хвоста и две головы (3 удара на каждые 4 хвоста);
    2. Рубим два хвоста, количество голов увеличивается на единицу и становится чётным;
    3. Рубим оставшиеся головы.

    strikes = tails//4*3 + 1 + (heads + 1)//2 = tails//4*3 + 2 + heads//2

  • Остаток от деления количества хвостов на 4 равен 3:

    1. Рубим по четыре хвоста и две головы (3 удара на каждые 4 хвоста);
    2. Рубим два хвоста, количество голов увеличивается на единицу и становится чётным;
    3. Делаем из оставшегося хвоста две головы (5 ударов) и рубим их (ещё 1 удар);
    4. Рубим оставшиеся головы.

    strikes = tails//4*3 + 1 + 6 + (heads + 1)//2 = tails//4*3 + 8 + heads//2

Итого мы получаем формулу следующего вида:

strikes = tails//4*3 + heads//2 + k

где k зависит от значений tails % 4 и heads % 2. Сведём все возможные значения k в таблицу:

И теперь мы можем занести эти данные в двумерный массив в нашей программе:

heads, tails = list(map(int, input('Введите количество голов и хвостов Горыныча: ').split()))

if heads % 2 == 1 and tails == 0:
    print('Увы, но бесхвостого Горыныча с нечётным количеством голов убить невозможно')
else:
    t = tails % 4
    h = heads % 2

    k = [[0,6,5,4],[4,3,2,8]]
    strikes = tails//4*3 + heads//2 + k[h][t]

    print(f"Минимальное количество ударов, за которое можно убить Горыныча: {strikes}")

Кроме того, в таблице прослеживаются определённые закономерности, и k можно было бы выводить из значений heads и tails с помощью такой формулы:

k = (7 - (tails % 4) - (heads % 2)*3) % 7

но к сожалению, она даёт неправильное решение для последней строки таблицы - вместо восьмёрки результат этого выражения равен единице. Но это единственное исключение можно исправить, добавив к результату 7, если heads % 2 == 1 и tails % 4 == 3:

k = (7 - (tails % 4) - (heads % 2)*3) % 7 + (tails % 4)//3 * (heads % 2) * 7

И соответственно нашу программу можно переписать альтернативным способом:

heads, tails = list(map(int, input('Введите количество голов и хвостов Горыныча: ').split()))

if heads % 2 == 1 and tails == 0:
    print('Увы, но бесхвостого Горыныча с нечётным количеством голов убить невозможно')
else:
    t = tails % 4
    h = heads % 2

    k = (7 - t - h*3) % 7 + t//3 * h * 7;
    strikes = tails//4*3 + heads//2 + k

    print(f"Минимальное количество ударов, за которое можно убить Горыныча: {strikes}")