QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #129902 | #6300. Best Carry Player 2 | bai_hong | WA | 1572ms | 3728kb | C++20 | 1.4kb | 2023-07-23 07:59:20 | 2023-07-23 07:59:24 |
Judging History
answer
#include<bits/stdc++.h>
#define int unsigned __int128
#define ll unsigned __int128
const ll inf=1e38;
using namespace std;
inline int read(){
char ch = getchar();int x = 0, f = 1;
while(ch<'0'||ch>'9'){if(ch == '-') f = -1;ch = getchar();}
while('0'<=ch && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
return x*f;
}
inline void write(int x){
if(x <0)putchar('-'),x =-x;
if(x >9)write(x /10);
putchar(x %10+'0');
}
int t,x,k,a[105];
ll f[222][222][2];
signed main(){
t=read();
while (t--){
x=read(),k=read();
int tx=x,n=0;
while (tx){ a[++n]=tx%10,tx/=10; } n+=k;
for (int i=1;i<=n+1;i++)
for (int j=0;j<=k;j++){
f[i][j][0]=inf;
f[i][j][1]=inf;
} f[n+1][0][0]=f[n+1][0][1]=0;
for (int i=n+1;i>=2;i--)
for (int j=0;j<=k;j++)
for (int kk=0;kk<2;kk++){
if (f[i][j][kk]==inf) continue;
for (int la=0;la<2;la++)
for (int s=0;s<=9;s++){
int tc=s+la+a[i-1];
int fl=(tc>=10);
if (kk!=fl) continue;
if (fl+j>k) continue;
f[i-1][j+fl][la]=min(f[i-1][j+fl][la],f[i][j][kk]*10+s);
}
}
int res=f[1][k][0];
if (res==inf){
puts("-1");
continue;
} else if (res==0){
int tc=0,i=1;
while (a[i]==9) tc++,i++;
putchar('1');
for (int i=1;i<=tc;i++)
putchar('0');
putchar('\n');
continue;
}
write(res);
putchar('\n');
}
return 0;
}
/*
1
90910190019900091 18
-----------------------------
909089809980099909
909089809980099909
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
1 54322 999999999987654322 9910
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
21 999990000099999 0 999990000099999 1 999990000099999 2 999990000099999 3 999990000099999 4 999990000099999 5 999990000099999 6 999990000099999 7 999990000099999 8 999990000099999 9 999990000099999 10 999990000099999 11 999990000099999 12 999990000099999 13 999990000099999 14 999990000099999 15 999...
output:
100000 10000 1000 100 10 1 900001 9900001 99900001 999900001 10000000001 9999910000 9999901000 9999900100 9999900010 9999900001 9000009999900001 99000009999900001 999000009999900001 99999999999999999900000000000000000 1000000000000000000
result:
ok 21 lines
Test #3:
score: -100
Wrong Answer
time: 1572ms
memory: 3616kb
input:
100000 119111011091190000 10 1911011191011999 16 110099199000119 0 19009911191091011 13 199090909919000900 17 19009010011919110 5 90910190019900091 18 10911100000101111 1 110090011101119990 4 100909999119090000 12 90901119109011100 2 111010119991090101 4 900991019109199009 5 100919919990991119 8 911...
output:
88988908810000 8088988808988001 10 88808908989 9800909090080999100 80890 809089809980099909 9 80010 9090000880910000 8900 9909 991 9008900 8880880090 8080090801 8009900808909899 80880898981 909 8800909 99988889901 89908888089 880908890980099000 100 9889801 81 808890008099900891 880990801 9998099 890...
result:
wrong answer 7th lines differ - expected: '909089809980099909', found: '809089809980099909'