A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.
Input
The first line contains integer t, the number of test cases. Integers K are given in the next t lines.
Output
For each K, output the smallest palindrome larger than K.
Example
Input: 2 808 2133 Output: 818 2222
Warning: large Input/Output data, be careful with certain languages
题意：输出比X大的第一个回文字符串。
思路：先把X按左半边为标准变成一个回文串X2，如果X2大于X，则输出X2。 否则变大X2 ：
如果X2全部为9，则需要加一位，变为首尾为‘1’，之间为‘0’的回文串。
否则，从之间开始找第一位非‘9’的位置，自加1。然后中间取余变为‘0’。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; const int maxn=1000010; char c[maxn],c2[maxn]; int T,N,Len,a[maxn]; bool check9() { for(int i=1;i<=Len;i++) if(c[i]!='9') return false; return true; } void Tochange() { for(int i=1;i<=Len/2;i++) c2[i]=c[i]; for(int i=Len/2+1;i<=Len;i++) c2[i]=c[Len+1-i]; } bool Toupper() { for(int i=1;i<=Len;i++) if(c2[i]>c[i]) return true; else if(c2[i]<c[i]) return false; return false; } int main() { int i,j; scanf("%d",&T); while(T--){ scanf("%s",c+1); Len=strlen(c+1); Tochange(); if(Toupper()) { for(i=1;i<=Len;i++) putchar(c2[i]); cout<<endl; continue; } if(check9()) { putchar('1'); for(i=1;i<Len;i++) putchar('0'); putchar('1'); cout<<endl; continue; } int np,Mid; if(Len&1) Mid=(Len+1)/2; else Mid=Len/2; for(np=Mid;np>=1;np--) if(c[np]!='9') break; c[np]++; for(i=np+1;i<=Mid;i++) c[i]='0'; for(i=1;i<=Mid;i++) putchar(c[i]); for(i=Len/2;i>=1;i--) putchar(c[i]); cout<<endl; } return 0; }