Как стать автором
Обновить

Комментарии 12

Вот спасибо)) Как раз искал какие-нибудь задачки) А тут еще и на новогоднюю тематику! =)
Code Wars тогда себе добавьте, там есть и на новогоднюю тематику тоже, в том числе довольно сложные.
Это было жестоко… Уже 3ий день не могу оторваться от задач. Сложные, местами, но затягивают. А система проверки решения — вообще нечто.
Попробуйте еще наш формат ru.hexlet.io/games ;)
Да, странно, что до сих пор не было поста. Участвую с первого дня, задачки забавные. Изредка даже удаётся в Leaderboard попасть.
Нет, подход «реши простые задачки, тогда откроем сложные» — это не очень интересно. Приятнее идти от самых трудных.
Вторая часть не принципиально сложнее первой. На самом деле, это скорее маленькое дополнительное условие.
Это повеселее. Сначала я их понял так, что дни можно открывать только по порядку.
Кстати, вторая задача про молекулу была NP-полной, или только квазиполиномиальной?
Да, NP-полная, насколько я понимаю. И вообще на самом деле это порождающая грамматика Хомского.

О решении усложнённой задачи про молекулу
В задаче про то как из e надо получить длинную молекулу я действовал полным перебором, но не пытаясь построить молекулу от е, а наоборот, пытаясь сократить результирующую молекулу до е, применяя правила в обратном порядке. Если при этом добавить некоторое количество «жадности» алгоритму, то есть сначала «сворачивать» максимально длинные подцепочки, то результат получается за какое-то совершенно смешное количество итераций. Мне интересно, а как другие её решали?
Скрытый текст
Я тоже шёл в обратную сторону. Но оказалось, что жадный алгоритм быстро попадает в тупик и не может из него выбраться. Анализ показал, что тупиком является цепочка CaRnFAr, перед которой не идёт атом Th (и возможно, несколько атомов Ca). После того, как я запретил эти цепочки, алгоритм быстро что-то нашёл.
Видимо, мне просто повезло со входными данными :)
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории