Электронный замок

Автор и разработчик задачи: Арсений Кириллов

Заметим, что мы всегда хотим получить более длинное число, так как длинное число больше короткого. Тогда для каждого $$$n$$$ можно посчитать метод динамического программирования, какую максимальную длину можно получить, если включено ровно $$$n$$$ сегментов. $$$len[n] = 1 + \max\limits_{x \in D}(len[{n - cost[x]}])$$$, где $$$cost[x]$$$ — количество горящих сегментов у цифры $$$x$$$, а $$$D$$$ — множество доступных цифр.

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