Забытый код
На калитке дачи стоит кодовый замок с k кнопками — цифрами от 0 до k − 1. Кнопки «ввод» у него нет: замок открывается, как только последние n нажатых цифр совпадут с кодом. Код вы забыли. Можно перебрать все коды по очереди, нажимая каждый целиком, — это n · kn нажатий. Но соседние попытки могут делить цифры: после нажатий 0 1 2 3 замок с n = 3 проверил и 012, и 123.
Выведите самую короткую последовательность нажатий, после которой замок гарантированно откроется, какой бы ни был код: в ней каждый из kn кодов должен встретиться подряд идущими цифрами. Если таких последовательностей несколько, подойдёт любая.
Вход
Два числа k и n (2 ≤ k ≤ 10, 1 ≤ n, kn ≤ 106).
Выход
Одна строка из цифр от 0 до k − 1 без пробелов — последовательность нажатий.
Примеры
Пример 1
2 3
0001011100
Пример 2
10 2
00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сколько нажатий нужно хотя бы? Первый код требует n цифр, а каждая следующая цифра даёт не больше одного нового кода.
2Подсказка 2
Состояние замка — последние n − 1 нажатых цифр. Каждое нажатие переводит его в новое состояние и заодно проверяет один код. Что в таком графе код — вершина или ребро?
3Идея
Вершины — строки из n − 1 цифры, их kn−1. Из вершины v нажатие цифры d ведёт в вершину «v без первой цифры, плюс d» и проверяет код «v, потом d». Каждый код — ровно одно ребро. Последовательность, проверяющая каждый код ровно раз, — путь, проходящий каждое ребро ровно раз, то есть эйлеров. Это граф де Брёйна: у каждой вершины k исходящих и k входящих рёбер, граф связен, значит, эйлеров цикл есть. Его длина — kn рёбер, а нажатий на n − 1 больше: сначала нужно попасть в стартовую вершину.
4Разбор
Вершину удобно хранить числом в системе счисления с основанием k: переход по цифре d — это (v · k + d) mod kn−1. Рёбра из вершины не нужно хранить вовсе: это просто цифры 0, 1, …, k − 1, и указатель ptr[v] помнит, какую цифру нажимать следующей. Дальше — Хирхольцер для ориентированного графа: стек пар «вершина, цифра, которой в неё пришли»; если у вершины на вершине стека остались цифры, нажимаем следующую, иначе выталкиваем её и записываем цифру в ответ. Ответ — n − 1 нулей (путь в стартовую вершину 0…0), а за ними цифры в обратном порядке выталкивания.
Нижняя оценка из первой подсказки совпадает с длиной цикла: n − 1 + kn. Поэтому ответ не просто хороший, а самый короткий. Для k = 10, n = 4 это 10 003 нажатия вместо 40 000.
4+Решение
5Сложность
O(kn): каждое ребро проходится один раз. Память — массив указателей на kn−1 вершин и стек до kn элементов.
6Типичные ошибки
- Жадность без графа. «Нажимать самую маленькую цифру, дающую новый код» быстро упирается в состояние, из которого все коды уже проверены, — и останавливается или ходит кругами. Правило «самая большая цифра» при старте с нулей работает (это конструкция Мартина 1934 года), но доказать это заметно труднее, чем построить эйлеров цикл.
- Рекурсивный обход. Глубина достигает kn = 106; рекурсия в Python упадёт.
- Код из одной цифры. При n = 1 вершина одна, и все рёбра — петли; ответ — все k цифр подряд, без лидирующих нулей.