Задача 5. Числа-палиндромы
Палиндромом называется строка, которая одинаково читается как слева направо, так и
справа налево. Рассмотрим все натуральные числа, запись которых в десятичной системе
счисления является палиндромом (при этом запись не начинается с нуля). Например, числа
121 и 1331 являются палиндромами, а число 123 — нет. По данному числу
N найдите
N-e в
порядке возрастания число-палиндром.
Программа получает на вход одно натуральное число
N, не превосходящее 100 000.
Программа должна вывести одно натуральное число —
N-е в порядке возрастания
число-палиндром.
Пример входных и выходных данных
Ввод
Вывод
20
111
Система оценивания
Решение, правильно работающее только в тех случаях, когда
N не превосходит 100,
будет оцениваться в 20 баллов.
Решение, правильно работающее только в тех случаях, когда
N не превосходит 1000,
будет оцениваться в 40 баллов.
Решение
На полный балл эта задача довольно сложна, но частничное решение, которое будет
набирать 40 баллов, написать довольно несложно. Для этого достаточно подряд перебирать
все числа, начиная с 1, и проверять, является ли число палиндромом. Когда будет обнаружено
N-е по
счету число-палиндром, необходимо вывести ответ.
Для проверки того, является ли число палиндромом,
заведем переменную
num_reversed, присвоив ей значение 0. Затем рассмотрим текущее число, будем получать его
цифры, начиная с конца по одной, для чего необходимо в цикле делить число нацело на 10.
Последней цифрой числа при этом будет остаток от деления числа на 10. Если внутри этого
Страница 6 из 8
цикла умножать число num_reversed на 10 и добавлять к нему последнюю цифру числа, то в
итоге в
переменной num_reversed получится значение исходного числа, записанное в
обратном порядке.
Вот пример цикла, в результате которого в переменную num_reversed
будет записана десятичная запись числа curr в обратном порядке:
num_reversed = 0
while num > 0:
num_reversed = num_reversed * 10 + num % 10
num //= 10
Полностью решение можно записать на языке Python следующим образом:
N = int(input())
i = 1
while N > 0:
num = i
num_reversed = 0
while num > 0:
num_reversed = num_reversed * 10 + num % 10
num //= 10
if num_reversed == i:
N -= 1
i += 1
print(i - 1)
Чуть более короткий вариант этого решения, которое для проверки, является ли число
палиндромом, преобразует его десятичную запись в строку, разворачивает эту строку в
обратном порядке и проверяет, что две получившиеся строки равны:
N = int(input())
i = 1
while N > 0:
if str(i) == str(i)[::-1]:
N -= 1
i += 1
print(i - 1)
Для решения на полный балл заметим, что существует 9 чисел-палиндромов длины 1
(это числа 1, 2, 3, …, 9), 9 чисел-палиндромов длины 2 (11, 22, 33, …, 99), 90
чисел-
палиндромов длины 3 (101, 111, 121, …., 999), 90 чисел-палиндромов длины 4 (1001, 1111,
1221, …, 9999), 900 чисел-палиндромов длины 5, 900 чисел-палиндромов длины 6, 9000
чисел-палиндромов длины 7, 9000 чисел-палиндромов длины 8, 90000 чисел-палиндромов
длины 9. Видно, что если исходное число не превосходит 100000, то ответ будет содержать не
более 9 цифр.
Поэтому сначала определим длину ответа и порядковый номер данного числа-
палиндрома среди всех чисел-палиндромов такой же длины, затем определим и само число-
палиндром.
Страница 7 из 8