Игры на графах

Доказательство ксора в функции Гранди методом таблички $2^k \times 2^k$

Задачи про Гранди

• Ним: за ход можно брать любое число камней из кучки
• Спички: за ход можно брать число спичек от $1$ до k$ $
• Ним, плюс ещё один ход: можно делить кучку на две
• Игра про Карлсона, Малыша и трёхмерную шоколадку
• Игры про пешки $3 \times N$
• Hacking Bush

Задачи про DP, терминатора и мужика

• Базовая версия, дополняем несколькими выходами, заклинаниями и т.д., в конце выписываем состояний [x1,y1,x2,y2,...,who]
• Кровожадный терминатор -- хочет как можно быстрее поймать
• Терминатор издевается -- хочет как можно медленнее, но поймать

Игра на большом дереве

• Игра путь из (1,1) в (N,N), первый минимизирует, второй максимизирует
• Игра на дереве размера $2^h$ за $O(2^h)$
• Вероятностное решение за $O(1.69^h)$
• Игра на дереве с весами = бинпоиск по ответу * $O(1.69^h)$