QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #131807 | #6300. Best Carry Player 2 | q | WA | 187ms | 3640kb | C++23 | 1.6kb | 2023-07-28 08:30:55 | 2023-07-28 08:30:57 |
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(i128 tmp=x;tmp;s[++n]=tmp%(i128)10,tmp/=(i128)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 ;
}
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: 1ms
memory: 3640kb
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: 3452kb
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: 187ms
memory: 3368kb
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'