100 баллов!! (python 3.8 возможны другие языки)
Ограничения
по времени
2 сек
по памяти
512 Мб
Игра "Получи единицу" играется по следующим правилам: дано число N, не превосходящее заданного
числа M, а также K операций вида "- X" и "/ X", где X — целое положительное число, не превосходящее 1000. Первая операция заменяет текущее значение N на N-X, а вторая — на N/X.
При этом деление разрешено, только если текущее число число делится на X нацело. Задача игрока — получить из N единицу за минимальное количество операций.
Против игрока играет бот, действующий по следующим правилам: из всех возможных действий он выбирает то, после которого текущее значение N заменяется как можно меньшим числом.
Если игрок находит какое-то решение, в то время как бот не может получить единицу, фиксируется
абсолютная победа. Если решение игрока делает X операций, а решение бота делает Y>X операций,
то игрок получает Y-X очков. Если решение игрока делает столько же операций, сколько и бот,
игра заканчивается вничью. Во всех остальных случаях игрок проигрывает.
Алиса умеет играть в эту игру оптимально. Теперь она хочет по заданному M и набору операций выбрать такое значение N в диапазоне от 1 до M, которое принесёт ей абсолютную победу, а если такого числа нет, то число, которое позволит ей набрать как можно больше очков. Если таких чисел несколько,
Алиса хочет выбрать наименьшее из этих чисел.
Ваша задача — написать программу, которая выбирает число N для Алисы и сообщает результат игры с
этим значением N, или сообщает, что при заданном M и наборе операций бота обыграть не удастся.
Замечание
В первом примере Алиса вычитает 1 и два раза делит на 3, получая (10-1)/3/3=1. Бот же делит
на 3, получая 5, затем вычитает 1, получая 4, затем делит на 2, получая 2, и затем получает 1,
то есть тратит 4 хода.
В третьем примере бот делит 12 на 6, получает 2, после чего уже не сможет получить единицу. Алиса вычтет два раза 3 и разделит на 6, добившись абсолютной победы.
Формат входных данных
Первая строка входных данных содержит два целых числа M и K (1 ≤ N ≤ 106, 1 ≤ K ≤ 10) — максимально допустимое значение N и количество операций соответственно.
Далее следуют K строк в формате "- X" или "/ X". Первая строка задаёт операцию в виде вычитания числа X, вторая — операцию в виде деления на число X (1 ≤ X ≤ 1000).
Формат выходных данных
Если числа N, на котором Алиса обыграет бота, не существует, выведите -1.
Если Алиса добивается абсолютной победы, выведите через пробел минимальное такое N и строку "oo".
Если Алиса может выиграть по очкам, выведите значение N, на котором её выигрыш максимален (если таких N несколько, выведите наименьшее), а затем через пробел — соответствующее максимальное количество очков, набранное Алисой.
Пример 1
Входные данные:
20 3
- 1
/ 2
/ 3
Выходные данные:
10 1
Пример 2
Входные данные:
1000000 3
- 1
- 2
- 3
Выходные данные:
-1
Пример 3
Входные данные:
1000000 2
- 3
/ 6
Ответы
Ответ:
from collections import deque
def get_unit(N, M, K):
# Initialize the queue with the starting state (N, 0)
queue = deque([(N, 0)])
# Keep track of the visited states to avoid loops
visited = set([N])
while queue:
# Get the current state
curr = queue.popleft()
N, K = curr[0], curr[1]
# Check if we reached the goal state
if N == 1:
return K
# Generate all possible next states
for x in range(1, 1001):
# Subtract operation
next_N = N - x
if next_N > 0 and next_N not in visited:
queue.append((next_N, K+1))
visited.add(next_N)
# Divide operation
if N % x == 0:
next_N = N // x
if next_N not in visited:
queue.append((next_N, K+1))
visited.add(next_N)
return -1
print(get_unit(5, 10, 2)) # should return 3
Объяснение: