Добрый день сообщество Codeforces!
Сегодня услышал такую задачу. Вы работаете полицейским в стране, где N городов и M дорог между ними (могут быть петли и кратные ребра). С тюрьмы, которая находиться в городе 1, сбежал преступник и известно, что если он попадет в город N, то там он сможет скрыться. За один день преступник может попасть в любой город, соседний с тем, где он находиться. В начале каждого дня Вы можете перекрыть одну дорогу, и она будет недоступна для преступника в все последующие дни. Преступник будет пойман в скором времени, если не доберется до города N. Определите, сможете ли Вы поймать преступника или он все же скроется?
2≤N≤100, 1≤М≤100
Известны ли ходы преступника?
нет, ведь мы можем перекрыть дорогу, по которой намеревался идти преступник, главное, что он бежит оптимально Оптимально-не значит по кратчайшему пути
Нет, ты меня не понял. Узнаем ли мы ход, который сделал преступник, после того, как он его сделал? Это важно. Задача без этих данных намного проще.
Да
Так. Чему меня научили сборы в Петрозаводске: если в голове нет гениальной и в то же время надежной идеи, как решить задачу с нужной асимптотикой — пиши медленное решение.
1) Это "медленное решение" может на реальных тестах работать быстрее, чем в теории
2) По ходу продумывания этого "медленного решения" откроются факты, которые впоследствии помогут написать быстрое решение
3) Может выясниться, что ответ на задачу — это n-е число Каталана. Или наоборот, выяснится, что нет(передаю привет andrewzta)
4) На худой конец, это "медленное решение" поможет стрессить гениальные, но не надежные, идеи быстрого решения.
Для начала напиши такой перебор за O(n * 2m). Пусть вор находится в i-й вершине и какая-то маска ребер уже вырезана полицейским. И пусть мы идем в обратную сторону: вместо того, чтобы вырезать ребра, мы добавляем ребра. Тогда выигрышными будут начальные состояния, в которых ребер нет, а вор находится не в последней вершине.