QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #131806 | #6300. Best Carry Player 2 | q | WA | 0ms | 3596kb | C++23 | 1.6kb | 2023-07-28 08:26:57 | 2023-07-28 08:27:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T> void read(T &x){ x=0; bool f=0; char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); if(f) x=-x; }
template<typename T> void write(T x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); }
}
const int U=38,C=20,K=2;
using i128=__int128;
int t;
int k,s[U];
i128 x,f[U][C][K],p[U];//f[i][j][0/1]表示当前考虑到第i位，进位了j次，当前位是否进位的最小答案
void init(){
p[0]=1;
for(int i=1;i<U;i++) p[i]=p[i-1]*(i128)10;
}
void work(){
IO::read(x),IO::read(k);
int n=0;
for(int tmp=x;tmp;s[++n]=tmp%10,tmp/=10);
n+=k;
if(!k){
int pos=n+1;
for(int i=1;i<=n;i++) if(s[i]!=9){
pos=i;
break;
}
putchar('1');
for(int i=1;i<pos;i++) putchar('0');
puts("");
return ;
}
// for(int i=n;i;i--) printf("%d",s[i]);
// puts("");
memset(f,0x3f,sizeof f);
i128 INF=f[0][0][0];
for(int i=0;i<=37;i++) f[i][0][0]=0;
for(int i=1;i<=37;i++){
// puts("ads");
for(int j=0;j<=min(i,k);j++){
f[i][j][0]=min(f[i][j][0],f[i-1][j][0]);
if(s[i]&&j) f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+p[i-1]*(10-s[i]));
if(j) f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+p[i-1]*(10-s[i]-1));
if(s[i]<9&&j) f[i][j][0]=min(f[i][j][0],f[i-1][j][1]);
}
}
i128 ans=min(f[n][k][0],f[n][k][1]);
IO::write(ans==INF?-1:ans),puts("");
}
int main(){
init();
// IO::write(p[38]);
IO::read(t);
for(;t--;) work();
return 0;
}
/*
4
12345678 0
12345678 5
12345678 18
990099 5
1
54322
999999999987654322
9910
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 0ms
memory: 3496kb
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:
1 9 90 89 3089 93089 493089 5493089 45493089 645493089 8645493089 98645493089 998645493089 9998645493089 99998645493089 999998645493089 9999998645493089 99999998645493089 999999998645493089 999999998430674944 1
result:
wrong answer 1st lines differ - expected: '100000', found: '1'