language: Python (python 2.7.2)
date: 104 days 6 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

'''
Created on 17-Jul-2011
 
@author: Naresh
'''
 
def nextPalindrome1(pal):
    length = len(pal)
    if (length & 1 == 0):
        if length == 0:
            return pal
        half = length >> 1 
        if (needsIncrement(pal, half -1, half, length)):
            return increment(pal, half -1, half, length)
        else:
            return pal[0:half-1] + pal[half-1]*2 +(pal[0:half-1])[::-1]
    else:
        if length == 1:
            if (pal == "9"):
                return (11)
            else:
                return int(pal) + 1
        half = length >> 1
        if (needsIncrement(pal, half, half, length)):
            return increment(pal, half, half, length)
        else:
            return pal[0:half] + pal[half] +(pal[0:half])[::-1]
    
def increment(pal, i, j, length):
    if (length & 1 == 0):
        temp = pal[0:i] + pal[i]*2 +(pal[0:i])[::-1]
    else:
        temp = pal[0:i] + pal[i] +(pal[0:i])[::-1]
    intPal = int(pal)
    while (int(temp) <= intPal):
        index = i
        while(index >= 0):
            if (temp[index] != "9"):
                break;
            index -= 1
        if (index == -1):
            temp = "1" + ("0" * (j)) + temp[j:length]
        else:
            temp = temp[0:index] + `int(temp[index]) + 1` + (i - index)*"0" + temp[i+1:length]
        length = len(temp)
        half = length >> 1
        if (length & 1 == 0):
            temp = temp[0:half-1] + temp[half-1]*2 +(temp[0:half-1])[::-1]
        else:
            temp = temp[0:half] + temp[half] +(temp[0:half])[::-1]
    return temp
 
def needsIncrement(pal, i, j, length):
    tempI = i
    tempJ = j
    
    while (i >= 0 and j < length):
        if (pal[i] < pal[j]):
            return True
        i-=1
        j+=1
 
    while (tempI >= 0 and tempJ < length):
        if (pal[tempI] != pal[tempJ]):
            return False
        tempI -= 1
        tempJ +=1
        
    if (tempI == -1 and tempJ == length):
        return True
    return False
import sys
import gc
import psyco
if __name__ == '__main__':
    strip = str.strip
    gc.disable()
    psyco.full()
    data = sys.stdin.readlines()
    for i in range(1, len(data)):
        input = strip(data[i])
        length = len(input)
        j = 0
        while (j < length):
            if (input[j] != '0'):
                break
            else:
                j+=1
        str = input[j:length]
        if (len(str) == 0 and len(input) > 0):
            print "1"
        else:
            print nextPalindrome1(str)