…закончился досрочно.
AND THE WINEEERRR IS...
Снимок Wolfgang Rzychon.
Здесь должна была быть дурацкая шутка про Диму Билана.
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 минут, чтобы пересечь мост. Пара передвигается со скоростью более медленного. Как перебраться на другую сторону в минимальное время?
