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

Question

Я пытаюсь решить проблему SPOJ 5: найти следующий по величине целочисленный «палиндром» для заданного ввода; то есть целое число, которое в десятичной нотации читает то же самое слева-направо и справа налево.

Пожалуйста, посмотрите вопрос here

Вместо того, чтобы использовать перебор, я пытаюсь вычислить следующий палиндром. Но мой код все еще возвращает TLE (то есть предел времени превышен), и я расстроен ... Не могли бы вы дать мне подсказку?

Вот мой код в питона 3.x

if __name__ == '__main__': 
    n = int(input()) 
    for i in range(n): 
     string = input() 
     length = len(string) 
     ans = "" 
     if length %2 == 0 : 
      half = length // 2 
      str_half = string[0:half] 
      ans = str_half + str_half[::-1]   
      if(ans <= string): 
       str_half = str(int(str_half) + 1) 
       ans = str_half + (str_half[0:half])[::-1] 
      print(ans) 
     else: 
      half = length // 2 
      str_half = string[0:half] 
      ans = str_half + string[half] + str_half[::-1] 
      if(ans<= string):    
       str_half = str(int(str_half+string[half]) + 1) 
       ans = str_half + (str_half[0:half])[::-1] 
      print(ans) 

Answer 1

Вход может быть длинным. В заявлении о проблеме говорится «не более 1000000 цифр». Так что, вероятно, есть несколько тестовых случаев с несколькими сотнями тысяч цифр. Разделение такой строки пополам, перемена одной половины и добавление их занимает немного времени. Но, насколько я знаю, обработка строк Python довольно хороша, так что это лишь небольшой вклад в проблему.

Что происходит с ? Время превращает строки такой длины в числа и огромные числа в строки. Для K = 10 ** 200000 + 2 только один шаг занял лишь один шаг: str_half = str(int(str_half+string[half]) + 1). Это может быть быстрее на вашем компьютере, но машины SPOJ довольно медленные, одно из таких событий может подтолкнуть вас к этому времени.

Таким образом, вам нужно избегать преобразований, работать непосредственно с представлениями строк (изменяемые списки цифр).

Answer 2

Так на основе этой проблемы позволяет выяснить, что самый длинный палиндром для случая, когда K.length == 1. Этот случай можно смело игнорировать, так как нет значения больше K, которое является палиндром K. То же самое относится к K.length == 2. Поэтому псевдокод оценить это выглядит следующим образом:

if K.length <= 2 
    pass 

Когда K.length == 3 значения мы заботимся о которых K [0] и K [2], это дает нам границы. Например, K == 100. значения, о которых мы заботимся, равны 1 и 0. Если K [0] больше, чем K [2], мы знаем, что мы должны сделать K [2] = K [0], и мы закончили. Другим примером является K == 200, первое значение больше 202, которое является первым простым, равным. Если K [0] == K [2] и K < 999, мы увеличиваем K [1] на 1, и мы закончили. Псевдокод следующим образом:

if K[0] > K[2] 
     K[2] = K[0] 
if K[0] == K[2] and K < 999 
     K[1]++ 

Если все значения в K являются 9 (999,9999, и т.д.) приращения K на 2 и закончить процесс. Я оставлю вам общую форму алгоритма, если вы в конечном счете не застряли.