首页 > 代码库 > 2016中国大学生程序设计竞赛（长春）-重现赛 1010Ugly Problem 回文数 模拟
2016中国大学生程序设计竞赛（长春）-重现赛 1010Ugly Problem 回文数 模拟
Ugly Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
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.
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\leq s \leq 10^{1000}).
For each test case, there is only one line describing the given integer s (1\leq s \leq 10^{1000}).
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题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5920
题意：将一个数拆成n（n<=50）个回文数的和。
题意：将一个数拆成n（n<=50）个回文数的和。
代码：
View Code
#include<iostream>#include<cstdio>#include<cstring>using namespace std;char s[2000];int ans[100][2000];int gg[100];int sub(int t,int len){ int i; for(i=len-1; i>=0; i--) { s[i]=s[i]-‘0‘-ans[t][i]; if(s[i]<0) { s[i]+=10+‘0‘; s[i-1]-=1; } else s[i]+=‘0‘; } for(i=0; i<len; i++) if(s[i]!=‘0‘) break; return i;}int main(){ int i,j,t,T; while(scanf("%d",&T)!=EOF) { getchar(); for(int asd=1; asd<=T; asd++) { scanf("%s",s); memset(ans,0,sizeof(ans)); int pre=0,len=strlen(s); t=0; while(pre<len) { int sign=1; for(i=pre,j=len-1; i<=j; i++,j--) { ans[t][i]=ans[t][j]=s[i]-‘0‘; if(ans[t][j]>s[j]-‘0‘) sign=0; else if(ans[t][j]<s[j]-‘0‘)sign=1; } gg[t]=pre; if(sign==0) { i--; ans[t][i]-=1; while(i>=0&&ans[t][i]<0) { ans[t][i]+=10; ans[t][i-1]-=1; i--; } for(i=pre,j=len-1; i<=j; i++,j--) ans[t][j]=ans[t][i]; if(ans[t][pre]==0) { ans[t][len-1]=9; gg[t]=pre+1; } } pre=sub(t,len); t++; } printf("Case #%d:\n",asd); printf("%d\n",t); for(i=0; i<t; i++) { for(j=gg[i]; j<len; j++) printf("%d",ans[i][j]); printf("\n"); } } } return 0;}
2016中国大学生程序设计竞赛（长春）-重现赛 1010Ugly Problem 回文数 模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。