Оптимальне альфа-бета відсікання
Лисиця Сіель розробляє штучний інтелект (ШІ) для гри. Ця гра описується як ігрове дерево 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 має структуру дерева.
Вихідні дані
Виведіть мінімальну кількість оцінок і максимальну кількість оцінок у листовому вузлі.
Будь ласка, розділіть пробілом мінімальну та максимальну кількість.