Лифт без четвёрок
В высоком доме этажи нумеруют подряд, но пропускают номера, в которых есть цифра 4 или две цифры 1 и 3 подряд: после 12 идёт 15, после 112 — 115, а 130–139 нет вовсе. Первый этаж — 1. Для каждого запроса N скажите, какой номер написан на кнопке N-го по счёту этажа.
Вход
В первой строке q (1 ≤ q ≤ 10⁵), дальше q чисел N (1 ≤ N ≤ 10¹⁵) по одному в строке.
Выход
Для каждого запроса — номер на кнопке, в отдельной строке. Он меньше 10¹⁶.
Примеры
Пример 1
6 1 3 4 12 13 100
1 3 5 15 16 123
Пример 2
4 10 11 30 31
11 12 35 36
Ограничения
- Время · Python
- 7000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сколько хороших номеров среди всех строк из L цифр? Это зависит только от L и от того, была ли перед ними единица.
2Подсказка 2
Зная, сколько хороших номеров начинается с 0, с 1, с 2…, можно выбрать первую цифру N-го: пропускать целые пачки, пока N не окажется внутри одной. Дальше — то же со следующей цифрой.
3Идея
Динамика по цифрам со спуском. f[L][s] — сколько строк из L цифр без четвёрок и без «13», если перед ними стояла единица (s = 1) или нет (s = 0). Ведущие нули не мешают: строки длины L — это числа от 0 до 10L − 1, и запрещённое сочетание в такой строке есть ровно тогда, когда оно есть в самом числе.
4Разбор
Нумеруем хорошие числа с нуля: 0 — номер 0, 1 — номер 1, … Тогда ответ — хорошее число с номером N. Длина L — наименьшая, при которой f[L][0] > N. Дальше по позициям: перебираем цифры по возрастанию, кроме 4 и кроме 3 после единицы; если пачка с этой цифрой (f[оставшихся][единица ли это]) не больше оставшегося номера, вычитаем её и идём к следующей цифре, иначе ставим эту цифру.
4+Решение
5Сложность
Таблица — 20 × 2 числа. Запрос — не больше 17 позиций по 10 цифр.
6Типичные ошибки
- Считать этажи по одному. Это
wrong.py: до миллионного этажа он ещё дойдёт, но запросов сто тысяч, и в четвёртом тесте времени уже не хватает, а номер этажа 10¹⁵ — шестнадцатизначный. - Забыть «13» на стыке. Состояние «была ли единица» нужно и для цифры, которую ставим, и для первой цифры пачки за ней: 113 запрещён, хотя ни 11, ни 3 сами по себе не плохи.
- Нумерация с единицы. Ноль в числе хороших — номер 0; если считать с единицы, ответ сдвинется на один этаж.
- Двоичный поиск по ответу тоже верен, но это 50 проходов по цифрам на запрос вместо одного спуска; на Python при ста тысячах запросов это ощутимо.