Оптимальная альфа-бета отсечка
Лисичка Сиэль разрабатывает искусственный интеллект (ИИ) для игры, которая представлена в виде игрового дерева T с n вершинами. Каждая вершина в игре имеет оценочное значение, отражающее качество ситуации. Это значение определяется как максимальное из значений дочерних узлов, умноженное на -1. Значения на листовых узлах оцениваются с помощью специальной функции Сиэль, которая является довольно ресурсоемкой. Поэтому она применяет альфа-бета отсечение для получения оценочного значения корневого узла, чтобы сократить количество вычислений на листовых узлах.
Порядок оценки дочерних узлов влияет на количество вычислений на листовых узлах. Поэтому Сиэль хочет знать минимальное и максимальное количество вычислений на листовых узлах, если она может оценивать дочерние узлы в произвольном порядке. Она попросила вас определить минимальное и максимальное количество оценок на листовых узлах.
Сиэль использует следующий алгоритм:
function negamax(node, α, β)
if node is a terminal node
return value of leaf node
else
foreach child of node
val := -negamax(child, -β, -α)
if val >= β
return val
if val > α
α := val
return α
Входные данные
Входные данные имеют следующий формат:
n
p_1 p_2 ... p_n
k_1 t_11 t_12 ... t_1k
...
k_n t_n1 t_n2 ... t_nk
Первая строка содержит целое число n, обозначающее количество вершин в игровом дереве T.
Вторая строка содержит n целых чисел p_i, представляющих оценочные значения для вершины i.
Далее следуют n строк, содержащих информацию о структуре дерева T.
k_i — это количество дочерних узлов вершины i, а t_ij — индексы дочерних узлов вершины i.
Входные данные подчиняются следующим ограничениям:
2 ≤ n ≤ 100
−10000 ≤ p_i ≤ 10000
0 ≤ k_i ≤ 5
2 ≤ t_ij ≤ n
Индекс корневого узла — 1.
Оценочное значение, кроме листового узла, всегда 0. Это не означает, что оценочные значения нелистовых узлов равны 0. Вы должны вычислить их, если это необходимо.
Листовой узел иногда имеет оценочное значение 0.
Дерево игры T имеет структуру дерева.
Выходные данные
Выведите минимальное и максимальное количество оценок на листовых узлах.
Пожалуйста, разделите пробелом минимальное и максимальное количество.