首页 > 代码库 > Ugly Problem

Ugly Problem

2024-08-16 07:38:10   220人阅读

Ugly Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Special Judge

Problem Description
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
2181000000000000
 

 

Sample Output
Case #1:299Case #2:29999999999991
Hint
9 + 9 = 18999999999999 + 1 = 1000000000000
分析：找一个较大回文数，然后大数相减；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<ll,int>#define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]const int maxn=1e3+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){    ll x=0;int f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,m,k,t,cnt,cas;char a[maxn],ans[52][maxn];string gao(string a, string b){    int lena = a.length();    int lenb = b.length();    int len = max(lena, lenb) + 5;    char res[len];    memset(res, 0, sizeof(res));    int flag, reslen = len;    len--;    res[len] = 0;    len--;    lena--; lenb--;    flag = 0;    while(lenb >= 0){        res[len] = a[lena--] - b[lenb--] + ‘0‘ - flag;        flag = 0;        if(res[len] < ‘0‘){            flag = 1;            res[len] = res[len] + 10;        }        len--;    }    while(lena >= 0){        res[len] = a[lena--] - flag;        flag = 0;        if(res[len] < ‘0‘){            flag = 1;            res[len] = res[len] + 10;        }        len--;    }    while((res[flag] == 0 || res[flag] == ‘0‘) && flag < reslen) flag++;    if(flag == reslen) return "0";    return res + flag;}void find(char*p,int now){    int i,len=strlen(p);    ans[now][len]=0;    for(int i=0;i<(len+1)/2;i++)        ans[now][i]=ans[now][len-1-i]=p[i];    bool flag=false;    for(int i=len/2-1;i>=0;i--)    {        if(p[i]<p[len-1-i])break;        else if(p[i]>p[len-1-i])        {            ans[now][i]--;            ans[now][len-1-i]--;            for(int j=i+1;j<len-1-i;j++)ans[now][j]=ans[now][len-1-j]=‘9‘;            break;        }    }    for(i=0;ans[now][i]==‘0‘;i++)    {        ans[now][len-1-i]=‘9‘;    }    strcpy(ans[now],ans[now]+i);    strcpy(a,gao(p,ans[now]).c_str());}int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        cnt=0;        scanf("%s",a);        while(strcmp(a,"0")!=0)        {            find(a,cnt);            cnt++;        }        printf("Case #%d:\n%d\n",++cas,cnt);        rep(i,0,cnt-1)printf("%s\n",ans[i]);    }    //system("Pause");    return 0;}
 

Ugly Problem


联系
我们