Sphere Judge Palindrome

Question

Я пытаюсь решить это: http://www.spoj.com/problems/PALIN/.I 'м, используя Python, и хотя он работает правильно, это кажется слишком медленным. Я пытаюсь найти способ улучшить производительность. Вот код:

case=raw_input(); 
l=int(case) 
cas=[] 

for k in range(0,l,1): 
    t=raw_input(); 
    cas.append(t) 


con=False 
print("") 
for k in range(0,l,1): 
var=int(cas[k])+1 
var=str(var) 
con= False 
while con != True: 


      n=int(var) 

      i=len(var) 
      j=-1 


      for i in range(i,0,-1): 
       j+=1 
       if var[i-1]==var[j]: 
        pass 
       else: 
        break 


       if i==1: 


        print var 
        con=True 
      n+=1 
      var=str(n) 

Любые предложения Спасибо заранее!

Answer 1

Вы пытаетесь установить найти палиндром. Он потребляет большую часть времени. Почему бы не попробовать построить это? Рассмотрим это:

1. Для чисел с четной длины (как 3133):

1.1. Убедитесь, что левая половина меньше или равна правой (т.е. 31 < = 33). Если это так, добавьте 1 к левой половине (31 + 1 = 32).

1.2. Инвертировать левую половину, чтобы построить палиндром: 32-> 23

1.3. Получите результат: '32' + '23' = '3223'

2. Для чисел с нечетной длиной вы должны сделать в основном то же самое, но обратите особое внимание на среднюю цифру. То есть в 809 левая половина (8) ниже правой (9), поэтому вам нужно добавить 1 к средней цифре, а затем построить палиндром с левой половиной: 818