ponder this

[avva]

(это тоже для программистов)

IBM продолжают публиковать нелегкую задачку для программистов (в широком смысле слова) каждый месяц. Задача за февраль, кажется, легче, чем обычно, ненамного выше по уровню, чем серьезное техническое интервью. Я решил ее на выходных, написав код на Питоне, где-то за два часа. Основная идея там - разобраться в том, как упростить происходящее, и потом как ловко оптимизировать вычисление, чтобы не на миллион лет.

Задача за март выглядит посложнее, забавная, с матрицами. Думаю и набросал кое-какой код, но пока не решил.

Comments

[dmitrmax.livejournal.com]

Ну в таком случае нужно применить метод динамического программирования. Прогнать для строки в 2-бита, получить все возможные пары (r,s) на конец прогона. Затем добавить 1 бит и выполнить все переходы из пар для 2-х бит в пары для 3-х бит. Пройдя половину пути можно выбрасывать пары, в которых r на столько большой, что уже точно не вернётся к нулю. Как-то так. Писать, если честно, лень )

[avva.livejournal.com]

Вообще-то найти надо как раз кол-во таких, где r не возвращается к нулю, а не где возвращается. А это может случится хоть в самом конце. Так что удачного прогона по O(2^42) кандидатам :)

[dmitrmax.livejournal.com]

Да, криво прочитал условие. Но (2^42 - Z), где Z - кол-во нулевых вариантов, спасёт отца русской демократии )

Ещё можно хранить вместо множества пар (r;s) ассоциативный массив (r;s)->k, где k - кол-во последовательностей, которые прогоняются до этого состояния. И тогда в конце можно получить количество вариантов для любого r.