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;
        }

    }
}