QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129234 | #6300. Best Carry Player 2 | wullaaa | WA | 1ms | 3644kb | C++14 | 1.2kb | 2023-07-22 11:20:16 | 2023-07-22 11:20:17 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=2e18;
ll pw[20],dp[20][20][2];
int k;
int main(){
pw[0]=1;
for(int i=1;i<=18;++i) pw[i]=pw[i-1]*10;
int T; scanf("%d",&T);
ll x;
while(T--){
scanf("%lld%d",&x,&k);
if(!k){
bool f=false;
for(int i=1;i<=18;++i) if((x/pw[i-1])%10!=9){ f=true,printf("%lld\n",pw[i-1]); break; }
if(!f) puts("-1");
continue;
}
int cnt=0;
while(x%10==0) x/=10,++cnt;
for(int i=0;i<=18;++i) for(int j=0;j<=k;++j) dp[0][j][0]=dp[0][j][1]=INF;
dp[0][0][0]=0;
for(int i=1;i<=18;++i){
int now=(x/pw[i-1])%10;
for(int j=0;j<=k;++j){
dp[i][j][0]=dp[i][j][1]=INF;
if(now!=9) dp[i][j][0]=dp[i-1][j][1];
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]);
if(j){
if(now) dp[i][j][1]=dp[i-1][j-1][0]+pw[i-1]*(10-now);
dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]+pw[i-1]*(9-now));
}
}
}
ll ans=min(dp[18][k][0],dp[18][k][1]);
if(ans==INF){ puts("-1");
cout<<x;
for(int i=1;i<=cnt;++i) cout<<0;
cout<<endl;
cout<<k<<endl;
}else{
printf("%lld",ans);
for(int i=1;i<=cnt;++i) printf("0");
puts("");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
1 54322 999999999987654322 9910
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3644kb
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 -1
result:
wrong answer 21st lines differ - expected: '1000000000000000000', found: '-1'