Здравствуйте. Не могли бы вы помочь решить следующую задачу, у меня точного текста условия нет к сожалению.
Задача называется "Странные числа".
Странное число - это число, каждая цифра которого, начиная со второй, имеет слева цифру, значение которой на единицу больше или меньше данной цифры . Необходимо найти все странные числа в диапазоне от n до m. (10 <= n, m <= 10^18)
1023, 1000000, 45367, 98 - странные числа
Спасибо.
Найти и вывести? Не слишком ли их много будет? Или требуется количество?
Может, это и бред, но на ум приходит динамика по профилю (длина префикса и какие цифры в нем встречаются). Но это пойдет только для подсчета количества.
Пусть текущий профиль P кодирует числа {an}. Тогда из состояния dp[i][P] мы можем сделать переход в состояние dp[i+1][P'] по любой из цифр ai +- 1, если новый префикс останется лексикографически меньше n.
А надо ли проще? Это же в реализации несложно, и по времени шикарно заходит.
Разве 1000000 странное число, ведь в условии написано, что "каждая цифра которого имеет слева цифру, значение которой на единицу больше или меньше данной цифры", для нулей неверно."...каждая цифра которого имеет слева цифру, значение которой на единицу больше или меньше данной цифры..."Для числа 1000000 слева есть пять позиций 0 для которых слева 0, а 0 ни больше 0 ни меньше 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.Поэтому можно делать рекурсивный перебор.кажется, вы тоже сначала невнимательно прочитали условие задачи :)