5920- Ugly Problem (string simulation && ideas)

Everyone hates ugly problems.  You are given a positive integer. You must represent that number by sum of palindromic numbers.  A palindromic number is a positive integer such that if you write out that integer as a string in decimal without leading zeros, the string is an palindrome. For example, 1 is a palindromic number and 10 is not.

Input

In the first line of input, there is an integer T denoting the number of test cases. For each test case, there is only one line describing the given integer s (1≤s≤101000).

Output

For each test case, output “Case #x:” on the first line where x is the number of that test case starting from 1. Then output the number of palindromic numbers you used, n, on one line. n must be no more than 50. en output n lines, each containing one of your palindromic numbers. Their sum must be exactly s.

Sample Input

2
18
1000000000000

Sample Output

Case #1:
2
9
9
Case #2:
2
999999999999
1

题意:

gives a number of fried chickens, and uses him to represent the sum of the number of palindromes within 50.

思维:

//Thoughts: Let a be the number given
While(a>=10)
{
    x=a;// take the first half
    X--;
    x+= reverse(x);
    a=a-x;
}

Solution:

#include <bits/stdc++.h>
Using namespace std;
Const int maxn = 1e3+10;
Bool getPal(char *s)//
{
    Int n=strlen(s);
    If(n==1) return 1;
    If(n==2&&s[0]=='1')
    {
        s[0]='9';
        s[1]=0;
        Return 0;
    }
    s[(n+1)/2-1]--;
    For(int i=(n+1)/2-1; i>0; i--) //minus one may have less than zero, analog subtraction
    {
        If(s[i]<'0')
            s[i]+=10,s[i-1]--;
    }
    If(s[0]=='0') //If the first digit is reduced, then all one is entered, which is less than the total number of digits.
    {
        For(int i=0; i<n; i++)
        {
            s[i]=s[i+1];
        }
        N--;
    }
    For(int i=(n+1)/2; i<n; i++)
        s[i]=s[n-i-1];
    Return 0;
}
Bool subStr(char *a, char *b)//calculates a-b, the result is stored in a, which is actually subtracting the constructed palindrome from s
{
    Int na = strlen(a);
    Int nb = strlen(b);
    For(int i=na-1,j=nb-1; j>=0; i--,j--)
    {
        If(a[i]>=b[j]) a[i] = a[i]-b[j]+'0';
        Else
            a[i]=a[i]+10-b[j]+'0',a[i-1]--;
    }
    Int p;
    For(p=0; a[p]=='0'; p++)
    {
        If(p==na)
            Return 1; //just finished, indicating equality
    }
    For(int i=0; p<=na; i++,p++)
        a[i]=a[p];
    Return 0;
}
Char s[maxn],ans[50][maxn];
Int cnt;
Int main()
{
    Ios::sync_with_stdio(false);
    Int t;
    Cin>>t;
    For(int cas=1; cas<=t; cas++)
    {
        Cin>>s;
        For(cnt=0;; cnt++)
        {
            Strcpy(ans[cnt],s);
            If(getPal(ans[cnt])||subStr(s,ans[cnt]))
                Break;
        }
        Printf("Case #%d:\n%d\n",cas,cnt+1);
        For(int i=0; i<=cnt; i++)
        {
            Printf("%s\n",ans[i]);
        }
    }
    Return 0;

}