SPOJ次のパインドーム

Question

私はSPOJの問題5を解決しようとしています。与えられた入力に対して次に大きな整数「回文」を探します。つまり、10進表記では、左から右、右から左に同​​じものを読み取る整数です。

代わりに力まかせ探索を使用しての質問here

のを見てください、私は次の回文を計算してみてください。しかし、私のコードはまだTLE（つまり、時間制限超過）を返すと私はイライラしています...私にヒントを与えてもらえますか？ここで

だから、その問題に基づいて

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)だけがここで約1秒かかりました。それはあなたのコンピュータでより速いかもしれませんが、SPOJのマシンは非常に遅いです、そのような出来事がそこに時間制限を押し進めさせるかもしれません。

変換を避けなければならないので、文字列表現（変更可能な数字のリスト）を直接操作する必要があります。

Answer 2

は最長の回文はK.length == 1の場合であるかを把握することができますのpython 3.xの中に私のコードです。このケースは、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]としなければならないことがわかります。もう1つの例は、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内のすべての値が2で9（999,9999など）増分Kであると処理を終了した場合。 最終的に詰まっていない限り、私はアルゴリズムの一般的な形式をあなたに任せます。