QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#19708 | #1183. Sum of Palindromes | JohnAlfnov | AC ✓ | 29ms | 3780kb | C++20 | 2.7kb | 2022-02-08 13:29:52 | 2022-05-06 06:46:05 |
Judging History
answer
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<ctype.h>
char s[100005],t[100005];
char A[26][100005];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
int i,j,n=strlen(s+1),tot=0;
int X=1;
while(s[X]=='0'||X+3<=n){
if(s[X]=='0'){
++X;
continue;
}
int flag=(s[X]!='1');
for(i=X+1;i<=n;++i)if(s[i]!='0'){
flag=1;
break;
}
if(!flag){
++tot;
for(int i=1;i<=n-X;++i)
A[tot][i]='9';
++tot;
A[tot][1]='1';
X=n+1;
break;
}
int Y=(X+n-1)>>1,Z=n-(Y-X);
for(i=1;i<=Y-X+1;++i)t[i]=s[i+X-1];
flag=(t[1]!='1');
for(int i=2;i<=Y-X+1;++i){
if(t[i]!='0')flag=1;
}
for(i=X;i<Y;++i)s[i]='0';
s[Y]='0'+flag;
if(flag){
int wz=Y-X+1;
--t[wz];
while(t[wz]<'0'){
t[wz]+=10;
t[wz-1]-=1;
--wz;
}
}
++tot;
for(i=1;i<=Y-X+1;++i)
A[tot][i]=t[i];
for(i=Y-X+2;i<=Z-X;++i)
A[tot][i]='0';
for(i=Z-X+1;i<=n-X+1;++i)
A[tot][i]=t[n+1-i-X+1];
for(i=n;i>=Z;--i){
char dy=t[Y-X+1-i+Z];
if(s[i]<dy){
s[i]=10+s[i]-dy+'0';
--s[i-1];
}else{
s[i]=s[i]-dy+'0';
}
}
int xx=Z-1;
while(xx>0&&s[xx]<'0'){
s[xx]+=10;
s[xx-1]-=1;
}
X=Y;
}
if(X==n-2){
if(s[n]>=s[X]){
++tot;
A[tot][1]=s[X];
A[tot][2]='0';
A[tot][3]=s[X];
s[n]=s[n]-s[X]+'0';
s[X]='0';
}else if(s[X]>'1'){
++tot;
A[tot][1]=s[X]-1;
A[tot][2]='9';
A[tot][3]=s[X]-1;
s[n]=s[n]+11-s[X]+'0';
s[X]='0';
}else{
++tot;
A[tot][1]='9';
A[tot][2]='9';
s[X]='0';
++s[n];
}
}
while(s[X]=='0')++X;
while(s[X]>='0'+10){
s[X]-=10;
s[X-1]+=1;
--X;
}
if(X==n-1){
if(s[X]==s[n]){
++tot;
A[tot][1]=s[X];
A[tot][2]=s[n];
X=n+1;
}else if(s[X]<s[n]){
++tot;
A[tot][1]=s[X];
A[tot][2]=s[X];
s[n]=s[n]-s[X]+'0',s[X]='0';
}else if(s[X]>'1'){
++tot;
A[tot][1]=s[X]-1;
A[tot][2]=s[X]-1;
s[n]=s[n]+11-s[X]+'0',s[X]='0';
if(s[n]=='0'+10){
s[n]-=10;
s[X]+=1;
}
}
}
while(s[X]>='0'+10){
s[X]-=10;
s[X-1]+=1;
--X;
}
while(s[X]=='0')++X;
if(X==n-1){
if(s[n]=='0'){
++tot;
A[tot][1]='9';
s[X]='0',s[n]='1';
}else{
++tot;
A[tot][1]='1';
A[tot][2]='1';
s[n]=s[n]-s[X]-1+'0';
}
}
while(s[X]=='0')++X;
if(X==n){
++tot;
A[tot][1]=s[X];
}
printf("%d\n",tot);
for(i=1;i<=tot;++i){
printf("%s\n",A[i]+1);
int B=strlen(A[i]+1);
for(j=1;j<=B;++j)A[i][j]=0;
}
for(i=1;i<=n;++i)s[i]='0';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3780kb
input:
2 378 2020
output:
3 303 66 9 3 1991 22 7
result:
ok OK!
Test #2:
score: 0
Accepted
time: 29ms
memory: 2112kb
input:
10128 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 9 1 1 11 2 11 1 2 11 2 2 11 3 2 11 4 2 11 5 2 11 6 2 11 7 2 11 8 2 11 9 3 11 9 1 1 22 2 22 1 2 22 2 2 22 3 2 22 4 2 22 5 2 22 6 2 22 7 2 22 8 2 22 9 3 22 9 1 1 33 2 33 1 2 33 2 2 33 3 2 33 4 2 33 5 2 33 6 2 33 7 2 33 8 2 33 9 3 33 9 1 1 44 2 44 1 2 44 2 2 44 3 2...
result:
ok OK!