QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129590 | #6300. Best Carry Player 2 | czc | WA | 612ms | 3660kb | C++14 | 1.4kb | 2023-07-22 21:02:58 | 2023-07-22 21:03:00 |
Judging History
answer
#include<bits/stdc++.h>
#define int unsigned __int128
using namespace std;
inline int read(){
char ch=getchar();int sum=0,f=1;
while(!isdigit(ch))f=(ch=='-')?-1:1,ch=getchar();
while(isdigit(ch))sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
return sum*f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
int T,a[42],dp[42][22][2];
int fast_pow(int x,int y){
int res=1;
for(;y;y>>=1,x=x*x)if(y&1)res=res*x;
return res;
}
signed main(){
T=read();
while(T--){
for(int i=0;i<=40;++i)a[i]=(int)0;
memset(dp,0x3f,sizeof(dp));
int op=dp[0][0][0];
char jk[20];int k;scanf("%s",jk+1);int n=strlen(jk+1);k=read();
for(int i=1;i<=n;++i)a[n-i+1]=jk[i]-'0';
if(k==0){
int czc=0;
for(int i=n;i>=1;i--){
if(a[i]==9) czc++;
else break;
}
cout<<1;
for(int i=1;i<=czc;i++){
cout<<0;
}
cout<<endl;
continue;
}
for(int i=0;i<=40;++i)dp[i][0][0]=0;
for(int i=1;i<=39;++i)
for(int j=0;j<=min(k,i);++j){
if(j>=1)dp[i][j][1]=min((a[i]==0?dp[i-1][j-1][1]+(9-a[i])*fast_pow(10,i-1):dp[i-1][j-1][0]+(10-a[i])*fast_pow(10,i-1)),dp[i-1][j-1][1]+(9-a[i])*fast_pow(10,i-1));
dp[i][j][0]=min(dp[i-1][j][0],(a[i]==9?dp[i-1][j][0]:dp[i-1][j][1]));
}
int ans=max((int)1,min(dp[39][k][0],dp[39][k][1]));
if(ans==op)puts("-1");
else write(ans),putchar('\n');
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3532kb
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: 3580kb
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: 612ms
memory: 3660kb
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 1 88808908989 9800909090080999100 80890 909089809980099909 9 80010 9090000880910000 8900 9909 991 9008900 8880880090 8080090801 8009900808909899 80880898981 909 8800909 99988889901 89908888089 980908890980099000 100 9889801 81 908890008099900891 880990801 9998099 8908...
result:
wrong answer 3rd lines differ - expected: '10', found: '1'