SPOJ-следующий палиндром

Question

Вопрос-

https://www.spoj.com/problems/PALIN/

-Входной номер контрольного примера

-Входной контрольный пример

-Выходближайший палиндромный номер к введенному контрольному коду, исключая сам кейс

Моя попытка -

t=int(input())
while t>0:
    k=int(input())
    rev=0
    while k!=rev:
        k=k+1
        no=k
        rev=0
        while no>0:
            rev=(rev*10)+(no%10)
            no=no//10
        if k==rev:
            print(k)
    t=t-1

Issue-

Я получаю «превышение лимита времени», но я не могу думать или найти более быструю программу.Ответы, которые я нахожу, действительно длинные и сложные.

Как мне исправить мой код?

Answer 1

Вы можете сэкономить много времени, рассматривая числа как строки, а не просто угадывая каждое возможное число и проверяя, является ли это палиндромом:

def next_pal(x):
    s = str(x)
    if len(s) % 2:  # odd
        # take the first half (including the middle digit)
        first_half = s[:len(s)//2+1]
        # construct a number that's that half,
        # plus itself reversed (without the middle digit)
        candidate = int(first_half + first_half[-2::-1])
        # that number could be smaller (e.g. if we started with 245)
        if candidate > x:
            return candidate
        # let's try again: we increment the first half and do the same thing:
        new_first_half = str(int(first_half) + 1)
        # but be careful: we could be adding a digit here (e.g. 999 -> 100001)
        if len(new_first_half) == len(first_half):
            return int(new_first_half + new_first_half[-2::-1])
        # instead, in those cases, we just return the smallest palindrome of that length
        return 10**len(s) + 1
    else:  # even
        # similar dance for even
        first_half = s[:len(s)//2]
        candidate = int(first_half + first_half[::-1])
        if candidate > x:
            return candidate
        new_first_half = str(int(first_half) + 1)
        if len(new_first_half) == len(first_half):
            return int(new_first_half + new_first_half[::-1])
        return 10**len(s) + 1

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