Задача оценивается в 00 баллов. Ограничение по времени работы в каждой задаче секунда

Задача 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

Вот пример полного решения на языке Python:
N = int(input())
currlen = 1
currcount = 9
while N > currcount:
N -= currcount
currlen += 1
currcount = 9 * 10 ** ((currlen - 1) // 2)
leftsize = (currlen + 1) // 2
rightsize = currlen - leftsize
leftpart = str(10 ** (leftsize - 1) + N - 1)
rightpart = leftpart[::-1]
if rightsize < leftsize:
rightpart = rightpart[1:]
print(leftpart + rightpart)
Возможен и другой вариант решения, в котором вместо циклов все возможные случаи
разбираются при помощи отдельный условий. Поскольку ответ содержит не более 9 цифр, то
можно разобрать только 9 случаев.
N = int(input())
if N <= 9:
print(N)
elif N <= 9+9:
s = str(N-9)
print(s + s)
elif N <= 9+9+90:
s = str(N-9-9+10-1)
print(s + s[-2::-1])
elif N <= 9+9+90+90:
s = str(N-9-9-90+10-1)
print(s + s[::-1])
elif N <= 9+9+90+90+900:
s = str(N-9-9-90-90+100-1)
print(s + s[-2::-1])
elif N <= 9+9+90+90+900+900:
s = str(N-9-9-90-90-900+100-1)
print(s + s[::-1])
elif N <= 9+9+90+90+900+900+9000:
s = str(N-9-9-90-90-900-900+1000-1)
print(s + s[-2::-1])
elif N <= 9+9+90+90+900+900+9000+9000:
s = str(N-9-9-90-90-900-900-9000+1000-1)
print(s + s[::-1])
else:
s = str(N-9-9-90-90-900-900-9000-9000+10000-1)
print(s + s[-2::-1])
Страница 8 из 8