Блог пользователя Droom

Автор Droom, 12 лет назад, По-русски

Формулировка задачи такая: найти количество чисел в промежутке между А и Б, которые делятся на Х и при этом не содержат запретных цифр(А<=Б,X натуральные, меньше 10^11 и больше нуля). Во входных данных сначала идет Х, потом и А и Б, и в следующей строке запретные цифры(по возрастанию, без дубликатов).

Пример теста 1

2 1 20 0123456789

Пример теста 2

1 1 100000000000 0123456789

Как такое решается? Перебор, понятное дело, проходить не должен)

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А такой перебор не зайдет?

for (int i = 1; ;i++)
{
   int d = i * x; //искомое число
  if (d > B)
    break;


   if (f(d) && d >= A && d <= B) // проверим что число не содержит запретных цифр и входит в нужный интервал
     ans++;



}
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Refactored:

    for (int d = ((a+x-1)/x)*x; d<=b; d+=x)
      if (f(d)) ans++;
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

      Это называется обфускация:) К тому же решение все равно TLное)

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Можно для относительно небольших X <= 1e6 посчитать ответ с помощью динамики. Стандартная динамика для чисел; состояния — текущая рассматриваемая позиция, остаток от деления на X; храним в динамике количество чисел с данным состоянием.

Для больших X можно просто перебрать все числа, делящиеся на X (и проверить в лоб остальные условия).

UPD. Не учел, что наши числа должны попадать в отрезок [A; B]. Ну тогда можно добавить в динамике поле, которое указывало на то, больше/меньше/равно ли наше число, суффикса числа T соответствующей длины. Тогда данная динамика считает количество чисел <= T, делящихся на X и не содержащих запретные цифры. Чтобы получить окончательный ответ можно просто посчитать величину f(B) — f(A — 1). f(T) — значение нашей динамики.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Точно при маленьких X будет TL, что-то про динамику и не подумал. Спасибо за понятное объяснение.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А можно немного подробнее с этой динамикой?

    Я не то чтобы настаиваю, просто еще не понимаю так сходу. Как это решение будет отбрасывать запрещенные числа и считать количество чисел с данным состоянием?

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      Ну просто переберем цифру, которую мы хотим поставить на текущую позицию(перебираем только среди разрешенных чисел). Теперь, если до этого у нас было число 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 — состояние больше/меньше

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Разве такое решение уложится в TL? взять, к примеру, тест: 1 1 10^11. Ваша динамика найдет 10^6 чисел, останется еще 10^11-10^6 ~ 10^11, многовато для перебора в лоб, по-моему. Или я неправильно Вас понял?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Динамика найдет все решения. Запускать перебор я предлагал только в случае больших X (т.е. либо задача решается перебором, либо динамикой)

»
12 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

есть еще перебор с meet in the middle. Делим число на 2 части, для каждого 0 ≤ i < X находим число легальных префиксов и число легальных суффиксов, при делении на X дающих в остатке i. Большие X и отсутствие запрещенных цифр считаем тривиально. Все получается порядка 2·107 операций в худшем случае

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Хорошая задача))) А откуда она?