QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129590#6300. Best Carry Player 2czcWA 612ms3660kbC++141.4kb2023-07-22 21:02:582023-07-22 21:03:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 21:03:00]
  • 评测
  • 测评结果:WA
  • 用时:612ms
  • 内存:3660kb
  • [2023-07-22 21:02:58]
  • 提交

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'