D&D Эпическая битва

Давно в голове вертится задачка, но всё никак не соберусь разобраться.

На узкой тропе встретились две партии приключенцев и не поделили “Тапочки Аццкой Силы +2″.
В партиях n1 и n2 приключенцев.
Для любой пары приключенцев из противоборствующих лагерей определён взаимный, не обязательно симметричный урон в процентах. Т.е. есть две матрицы D1[n1][n2] и D2[n2][n1] определяющие, сколько процентов здоровья отымет приключенец i, накатив супостату j. В матрицах могут быть нули — например, кто-то неуязвим для определённых противников.
На каждом ходу каждый приключенец обеих партий выбирает себе жертву и наносит удар.
После хода приключенцы со здоровьем <=0 считаются погибшими.

Каков исход битвы (победа одной из партий, взаимное уничтожение или невозможность продолжать бой)?

Красивая задачка

В журнале spamsink.livejournal.com была опубликована такая вот задачка:

На одной из центральных клеток шахматной доски стоит “ладьекороль” (фигура, которая ходит на одну клетку, но только по вертикали или горизонтали), оставляющий следы на клетках, на которых он побывал. Он делает случайные равновероятные ходы до тех пор, пока на доске не окажется 4 клетки со следами, включая первоначальную. В результате следы образуют одну из пяти (зеркальные считаются идентичными) фигур тетрамино: S, T, O, L, I. Какова вероятность получить каждую из фигур?

Google Code Jam задачка

На GCJ 2008 во втором туре предлагалась задачка Cheating on a Boolean Tree. Судя по статистике, задачка простая, но мне бы хотелось показать, как работает Branch & Bound метод.

Дано двоичное дерево. Листья дерева помечены булевыми значениями. Внутренние узлы – операторами AND и OR и имеют по два подузла. Операторы некоторых узлов можно менять. Изменить значение корня дерева на заданное, поменяв минимальное кол-во операторов.

Жизнь – это очень узкий мост…

В замечательной книжке “How to Solve It: Modern Heuristics” Z.Michalewicz и D.Fogel перед каждой главой предлагается решить пару тривиальных задачек, обобщения которых приводят к интересным проблемам.

Вот одна из таких задачек:

Четыре путника разных лет подошли ночью к мосту. Мост узок – только два человека могут пройти по нему одновременно. Также имеется только одна лампа. Путникам требуется 1, 2, 5 и 10 минут, чтобы пересечь мост. Пара передвигается со скоростью более медленного. Как перебраться на другую сторону в минимальное время?