Формулировка задачи такая: найти количество чисел в промежутке между А и Б, которые делятся на Х и при этом не содержат запретных цифр(А<=Б,X натуральные, меньше 10^11 и больше нуля). Во входных данных сначала идет Х, потом и А и Б, и в следующей строке запретные цифры(по возрастанию, без дубликатов).
Пример теста 1
2 1 20 0123456789
Пример теста 2
1 1 100000000000 0123456789
Как такое решается? Перебор, понятное дело, проходить не должен)
А такой перебор не зайдет?
Refactored:
Это называется обфускация:) К тому же решение все равно TLное)
Можно для относительно небольших X <= 1e6 посчитать ответ с помощью динамики. Стандартная динамика для чисел; состояния — текущая рассматриваемая позиция, остаток от деления на X; храним в динамике количество чисел с данным состоянием.
Для больших X можно просто перебрать все числа, делящиеся на X (и проверить в лоб остальные условия).
UPD. Не учел, что наши числа должны попадать в отрезок [A; B]. Ну тогда можно добавить в динамике поле, которое указывало на то, больше/меньше/равно ли наше число, суффикса числа T соответствующей длины. Тогда данная динамика считает количество чисел <= T, делящихся на X и не содержащих запретные цифры. Чтобы получить окончательный ответ можно просто посчитать величину f(B) — f(A — 1). f(T) — значение нашей динамики.
Точно при маленьких X будет TL, что-то про динамику и не подумал. Спасибо за понятное объяснение.
А можно немного подробнее с этой динамикой?
Я не то чтобы настаиваю, просто еще не понимаю так сходу. Как это решение будет отбрасывать запрещенные числа и считать количество чисел с данным состоянием?
Ну просто переберем цифру, которую мы хотим поставить на текущую позицию(перебираем только среди разрешенных чисел). Теперь, если до этого у нас было число x, то сейчас стало число x + dig * 10^pos, где pos — номер позиции, куда мы ставим нашу цифру(соответственно пересчитать остаток несложно).
Пересчет состояния больше/меньше вроде бы тоже не очень сложный. Например: если наше текущее сгенерированное число x было меньше соответствующего суффикса, и мы приписываем к нему цифру dig, которая больше чем соответствующая цифра в нашем числе, то новое число будет больше соответствующего суффикса. Ну и остальные варианты аналогично.
UPD. Ну а теперь мы из некоторого состояния [pos][mod1][eq1] хотим перейти в состояние [pos + 1][mod2][eq2]. Ну т.е. количество чисел со вторым состоянием увеличилось на количество чисел с первым состоянием (dp[pos + 1][mod2][eq2] += dp[pos][mod1][eq1]). eq — состояние больше/меньше
Разве такое решение уложится в TL? взять, к примеру, тест: 1 1 10^11. Ваша динамика найдет 10^6 чисел, останется еще 10^11-10^6 ~ 10^11, многовато для перебора в лоб, по-моему. Или я неправильно Вас понял?
Динамика найдет все решения. Запускать перебор я предлагал только в случае больших X (т.е. либо задача решается перебором, либо динамикой)
Окей, разобрался.
есть еще перебор с meet in the middle. Делим число на 2 части, для каждого 0 ≤ i < X находим число легальных префиксов и число легальных суффиксов, при делении на X дающих в остатке i. Большие X и отсутствие запрещенных цифр считаем тривиально. Все получается порядка 2·107 операций в худшем случае
Хорошая задача))) А откуда она?
С университетских отборов к KPI-Open.
А вообще, она с COCI 2007 :)
Я точно такую задачу решал на Qbit, 2 или 3 года назад.