Ugly Problem

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 812????Accepted Submission(s): 286
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

  
  
   
   2 18 1000000000000
  
  

?

Sample Output

  
  
   
   Case #1: 2 9 9 Case #2: 2 999999999999 1 
   
    
     
     Hint 
     
     9 + 9 = 18 999999999999 + 1 = 1000000000000  
   
   
    
  
  

?

题意：将一个数s (1<=s<=10^1000) 拆成不超过50个回文数， 这些回文数相加等于s。 要求输出这样的数的个数，并从小到大输出这些数。

题解：每次都构造当前<=s的近似最大的回文数build?，然后 s=s-build 。 ?用字符串表示的时候注意写法就行了。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1010
struct Node
{
	char num[maxn];
	int len;
}ans[102];//ans数组开在main函数厉害爆栈了 

Node detail(Node str)//构造一个较大的回文数 
{
	int temp=str.len/2+1;
	str.num[temp]--;
	for(int i=temp;i<=str.len;++i)
		if(str.num[i]<'0')
		{
			str.num[i+1]--;
			str.num[i]+=10;
		}
	if(str.num[str.len]=='0')
		str.len--;
	for(int i=1;i<=str.len/2;++i)
		str.num[i]=str.num[str.len-i+1];
	return str;
}

Node sub(Node res,Node subtor)//大数相减 
{
	for(int i=1;i<=subtor.len;++i)
	{
		if(res.num[i]>=subtor.num[i])
			res.num[i]=res.num[i]-subtor.num[i]+'0';
		else
		{
			res.num[i+1]--;
			res.num[i]+=10;
			res.num[i]=res.num[i]-subtor.num[i]+'0';
		}
	}
	for(int i=res.len;i>0;--i)
	{
		if(res.num[i]=='0')
			res.len--;
		else	break;
	}
	return res;
}

int main()
{
	int t,k=1;
	scanf("%d",&t);
	while(t--)
	{
		Node str;
		memset(ans,sizeof(ans));
		scanf("%s",str.num+1);
		str.len=strlen(str.num+1);
		for(int i=1;i<=str.len/2;++i)//反转字符串，让高位表示高数位 
			swap(str.num[i],str.num[str.len-i+1]);
		int cnt=0;
		while(str.len>1)
		{
			if(str.len==2&&((str.num[1]-'0'+(str.num[2]-'0')*10)<20))
			{
				ans[cnt].num[1]='9';
				ans[cnt++].len++;
				str=sub(str,ans[cnt-1]);
				continue;
			}
			Node build=detail(str);
			ans[cnt++]=build;
			str=sub(str,ans[cnt-1]);
		}
		ans[cnt++]=str;
		printf("Case #%d:\n%d\n",k++,cnt);
		for(int i=0;i<cnt;++i)
		{
			for(int j=ans[i].len;j>=1;--j)
				putchar(ans[i].num[j]);
			printf("\n");
		}
	}
	return 0;
}