Блог пользователя vova.bogatyrev

Автор vova.bogatyrev, 16 лет назад, По-русски
Здравствуйте. Не могли бы вы помочь решить следующую задачу, у меня точного текста условия нет к сожалению. 
Задача называется "Странные числа".
Странное число - это число, каждая цифра которого, начиная со второй, имеет слева цифру, значение которой на единицу больше или меньше данной цифры . Необходимо найти все странные числа в диапазоне от n до m. (10 <= n, m <= 10^18)

1023,  1000000, 45367, 98 - странные числа


Спасибо.
  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

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

Найти и вывести? Не слишком ли их много будет? Или требуется количество?

Может, это и бред, но на ум приходит динамика по профилю (длина префикса и какие цифры в нем встречаются). Но это пойдет только для подсчета количества.

  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    извините, нельзя ли поподробнее
    • 16 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится
      динамика от длины обработанного префикса и 10 чисел 0 или 1, показывающих, использована ли в префиксе соответствующая цифра
      переходы очевидны
      за 18*10*2^10 зайдет отлично
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Пусть текущий профиль P кодирует числа {an}. Тогда из состояния dp[i][P] мы можем сделать переход в состояние dp[i+1][P'] по любой из цифр ai +- 1, если новый префикс останется лексикографически меньше n.

      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Дополню, что профиль здесь - десятибитовое число, каждый бит которого кодирует, встречалась ли нам соответствующая цифра ранее. Например, профиль P = 0110001011 (он же является числом 395), кодирует, что в префиксе встречались цифры 0, 1, 3, 7 и 8. Если мы дописываем к числу цифру X, X-ый бит профиля надо сделать равным 1.
16 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
Разве 1000000 странное число, ведь в условии написано, что "каждая цифра которого имеет слева цифру, значение которой на единицу больше или меньше данной цифры", для нулей неверно.
Невнимательно прочел...
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
только количество
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    тогда алгоритм LooNaTeg вполне подойдет
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится
    Тогда действительно можно делать динамикой по профилю. Мы умеем считать  количество k-значных странных чисел, меньших n (для этого не надо делать переход, если текущий префикс становится лексикографически больше префикса числа) за 2^10 * 10 * len (количество профилей, количество переходов, длина числа). Как из этого посчитать количество чисел от m до n, думаю, понятно.
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      я не совсем понимаю как можно по профилю определить текущий префикс, ведь если профиль допустим равен 0000001110, то префиксы могут быть 32321 и 32123, и нельзя определить больше или меньше текущий префикс префикса числа 
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, смотри. В профиле мы будем хранить, какие числа на данный момент уже встретились. Сам порядок не важен, они все будут слева нового числа.

        И да,
        3 дня назад, # ^
           +5 
        В профиле единичные биты всегда идут подряд, достаточно хранить диапазон уже встретившихся в числе цифр
        значит тебе достаточно хранить только границы диапазона уже встреченных чисел.
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Рассматривай только числа меньшие заданного.
        НО предварительно рассчитай для числа равного заданному и из его ситуаций походи во все возможные в массиве меньших. Если на каком-то шаге само число не удовлетворяет условию,то останавливаешься, иначе из него увеличиваешь значения массива. Если все число целиком удовлетворяет - добавляй к ответу 1. 
        Массив меньших строишь как хочешь уже: если префикс рассматриваемого числа меньше префикса верхней границы можно ходить куда угодно( с учетом профиля само-собой)
16 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
Да, странно что число 1000000 странное)))
Вообще чисел будет не много - на каждом шаге есть только 2 пути (а для 0 и 9 так вообще 1 путь) поэтому грубая оценка странных чисел длины L будет 9*2^(L-1) (9 потому что с нуля начинаться не может). Соответственно общее количество странных чисел будет сумма 9*2^(i-1) где i=1..18, что равно 9*2^18 = 2 359 296.

Поэтому можно делать рекурсивный перебор.

16 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
Такой вопрос: странные числа должны начинаться с единицы (слева как бы находятся невидимые ведущие нули), или первой цифры числа условие не касается?
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
а можно ссылку на задачу? хочется сдать попробовать