Hi guys, the following is my python code for the PALIN. The algorithm is fine, i think, however the server returns 'time limit exceeded'. I don't know what's wrong. can anybody help me out? thanks a lot.
def next_palindrome(exp):
exp = list(exp)
half = len(exp) / 2
if len(exp) % 2 != 0:
already_bigger = False
for i in range(half):
if already_bigger == False and int(exp[len(exp) - 1 - i]) < int(exp[i]):
already_bigger = True
exp[len(exp) - 1 - i] = exp[i]
if already_bigger == False:
if exp[half] != '9':
exp[half] = str(int(exp[half]) + 1)
else:
while half > 0:
exp[half] = '0'
if exp[half - 1] != '9':
temp = str(int(exp[half - 1]) + 1)
exp[half - 1] = temp
exp[len(exp) - 1 - half + 1] = temp
break
else:
exp[half - 1] = '0'
exp[len(exp) - 1 - half + 1] = '0'
half -= 1
else:
res =['1']
res.extend(exp)
res[len(res) - 1] = '1'
exp = res
# len(exp) % 2 == 0
else:
already_bigger = False
for i in range(half):
if already_bigger == False and int(exp[len(exp) - 1 - i]) < int(exp[i]):
already_bigger = True
exp[len(exp) - 1 - i] = exp[i]
if already_bigger == False:
if exp[half - 1] != '9':
temp = str(int(exp[half - 1]) + 1)
exp[half - 1] = temp
exp[len(exp) - 1 - half + 1] = temp
else:
while half - 1 > 0:
exp[half - 1] = '0'
exp[len(exp) - 1 - half + 1] = '0'
if exp[half - 2] != '9':
temp = str(int(exp[half - 2]) + 1)
exp[half - 2] = temp
exp[len(exp) - 1 - half + 2] = temp
break
else:
exp[half - 2] = '0'
exp[len(exp) - 1 - half + 2] = '0'
half -= 1
else:
res = ['1']
res.extend(exp)
res[len(res) - 1] = '1'
exp = res
import string
exp = string.join(exp, '')
return exp
if __name__ == '__main__':
num = int(raw_input())
for i in range(num):
inp = raw_input()
print next_palindrome(inp)
