LightOJ 1396 Palindromic Numbers (III)（贪心）

Description

Vinci is a little boy and is very creative. One day his teacher asked him to write all the Palindromic numbers from 1 to 1000. He became very frustrated because there is nothing creative in the task. Observing his expression, the teacher replied, “All right then, you want hard stuff, you got it.” Then he asks Vinci to write a palindromic number which is greater than the given number. A number is called palindromic when its digits are same from both sides. For example: 1223221, 121, 232 are palindromic numbers but 122, 211, 332 are not. As there can be multiple solutions, Vinci has to find the number which is as small as possible.

Input

Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with a line containing a positive integer. This integer can be huge and can contain up to 105 digits.

Output

For each case, print the case number and the minimum possible palindromic number which is greater than the given number.

Sample Input

5

121

1

1332331

11

1121

Sample Output

Case 1: 131

Case 2: 2

Case 3: 1333331

Case 4: 22

Case 5: 1221

我想说。。这是一道令人难过的。。。模拟题。。。

要使数字串成为比原串大的回文串，并且这个数字要尽量的小。

1）如果它已经是一个回文串了，因为要尽量小，我们肯定是要最中心的数字变大。

2）如果它不是一个回文串，那我们肯定要进行修改，先把它改成一个尽量小回文串（修改后半段数），再考虑这个回文串与原串的大小关系。回到1）。

实现：

我是用递归，solve（0，n-1），从两头向中间修改。其中需要用一个全局变量来记录之前的改变使得当前串变大还是变小了。如果是变小了，那么最中心的数字必须变大，如果变大了，最中心的数字可以不变。

细节：如果是299992 这种数，就要变成300003.

如果是9999 这种，变成10001，需要特殊输出。

一把辛酸泪TUT！！！！！

细节决定成败。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define mem(array) memset(array,0,sizeof(0))
int t,n,ans,da;
char a[],s[];
int solve(int l,int r)
{
    if(l==r) 
    {
        if(da==) 
        { 
            s[r]++;
            if(s[r]>'9') 
                {
                    s[r]='0';
                    return ;
                }
        }
        return ;
    }
    if(s[l]>s[r]) da=;
    if(s[l]<s[r]) da=;
    s[r]=s[l];
    if(l+==r){
        if(da) return ;
        else {
            s[l]++;
            s[r]++;
            if(s[l]>'9') {  
                s[l]='0';
                s[r]='0';
                return ;
            }
            else return ;
        }
    }
    if(solve(l+,r-)) {
        s[l]++;
        s[r]++;
        if(s[l]>'9') {
            s[l]='0';
            s[r]='0';
            return ;
        }
    }
    return ;
}
int spp()
{
    cout<<;
    for(int i=;i<n-;i++)
        cout<<s[i];
    cout<<<<endl;
    return ;
}
int main()
{
    freopen("in.txt","r",stdin);
    scanf("%d\n",&t);
    for(int k=;k<=t;k++)
    {
        gets(s);
        n=strlen(s);
        da=;
        int x=solve(,n-);
        printf("Case %d: ",k );

        if(x) spp();
        else 
        {
            for(int i=;i<n;i++) cout<<s[i];
            cout<<endl;
        }

    }
}