Question

деякому царстві жив Змій Горинич. У нього було N голів та M хвостів. Іван-царевич вирішив знищити губителя людських душ, для чого йому його кума Баба Яга подарувала чарівний меч, оскільки тільки ним можна вбити Змія Горинича. Якщо відрубати одну голову, то на її місці виростає нова, якщо відрубати хвіст, то замість нього виросте 2 хвости. Якщо відрубати два хвости, то виросте 1 голова, і тільки коли зрубати 2 голови, то не виростає нічого. Змій Горинич гине тільки в тому випадку, коли йому відрубати всі голови і всі хвости. Визначити мінімальну кількість ударів мечем, потрібну для знищення Змія Допоможіть будь-ласка.Даю 30 балів.До 13 квітня.

Answer 1

Ответ:

from collections import deque

# Вхідні дані: кількість голів та хвостів Змія Горинича

n, m = map(int, input().split())

# Створення вершини графа, що відповідає початковому стану

start_node = (n, m)

# Створення черги та додавання початкової вершини

queue = deque([start_node])

# Створення множини відвіданих вершин

visited = set([start_node])

# Ініціалізація змінної, що зберігатиме кількість ударів мечем

num_hits = 0

# Поки черга не пуста

while queue:

   # Збільшення лічильника ударів мечем

   num_hits += 1

   

   # Кількість вершин на поточному рівні глибини

   level_size = len(queue)

   

   # Обробка всіх вершин на поточному рівні глибини

   for i in range(level_size):

       # Отримання вершини з початку черги

       node = queue.popleft()

       

       # Перебір всіх можливих дій

       for action in

Объяснение:

Answer 2

Для вирішення цієї задачі давайте розглянемо різні сценарії і знайдемо мінімальну кількість ударів мечем, потрібну для знищення Змія Горинича.

1. Почнемо з початкового стану, коли у Змія Горинича є N голів та M хвостів.

2. Якщо відрубати одну голову, на її місці виростає нова. Тому для знищення голів нам потрібно зробити N ударів мечем.

3. Тепер розглянемо хвости. Якщо відрубати один хвіст, то на його місці виросте 2 нових хвости. Тобто, ми можемо знищити хвости шляхом відрубання одного хвоста до тих пір, поки їх не залишиться менше, ніж N. Давайте знайдемо кількість ударів мечем, потрібних для цього:

   • Спочатку M = M - 1 хвіст (1 удар).
   • Тепер M = 2 * M, бо на місці одного хвоста виросте 2 (0 ударів).
   • Повторюємо це дійство доти, доки M не стане менше, ніж N.

4. Тепер, коли M стало менше, ніж N, ми можемо відрубати по два хвости і на їхньому місці буде виростати 1 голова, до тих пір, поки N і M не стануть рівні. Для цього нам потрібно відрубати хвости доти, доки різниця між N і M не стане кратною 2 (щоб позбутися голів).

5. На цьому етапі у нас залишилася одна голова та один хвіст. Щоб знищити Змія Горинича, відрубайте дві голови (1 удар) і два хвости (1 удар).

Отже, загальна кількість ударів мечем дорівнює N (голів) + кількість ударів для знищення хвостів + 1 (останній удар для знищення останньої голови та хвоста).

Підсумовуючи, формула для обчислення мінімальної кількості ударів мечем така:

Кількість ударів = N + (M - N) + (M % 2) + 1

Де:

• N - початкова кількість голів
• M - початкова кількість хвостів
• M % 2 - залишок від ділення M на 2 (щоб знайти кількість ударів для знищення останньої голови та хвоста)
• +1 - останній удар для знищення останньої голови та хвоста

Будь ласка, вставте в цю формулу значення N та M, і ви отримаєте мінімальну кількість ударів мечем, потрібну для знищення Змія Горинича.