QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690876#6300. Best Carry Player 2IdtwteiWA 1ms3812kbC++141.4kb2024-10-31 07:18:532024-10-31 07:18:53

Judging History

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

  • [2024-10-31 07:18:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3812kb
  • [2024-10-31 07:18:53]
  • 提交

answer

#include <bits/stdc++.h>
#define int __int128
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;

const int INF=1e36;

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : f, c = getchar();
	while (c >= '0' && c <= '9') x = (x<<3)+(x<<1)+(c^48), c = getchar();
	return x*f;
}

inline void write(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x/10);
	putchar('0'+x%10);
}

const int N = 20;
int lim = 19, a[N], w[N], f[N][N][2];

inline void upd(int &x, int y) { x = y < x ? y : x; }

inline void solve() {
	int x = read(), k = read(), cnt = 0;
	if (!k) {
		while (x%10 == 9) ++cnt, x /= 10;
		return (void)(write(w[cnt+1]), enter);
	}
	for (int i = 1; i <= lim; ++i) a[i] = x%10, x /= 10;
	for(int i=0;i<=lim;++i) for(int j=0;j<=k;++j) f[i][j][0]=f[i][j][1]=INF; f[0][0][0] = 0;
	for (int i = 1; i <= lim; ++i)
		for (int j = 0; j <= k; ++j) {
			upd(f[i][j][0], f[i-1][j][0]);
			if (a[i] < 9) upd(f[i][j][0], f[i-1][j][1]);
			if (!j) continue;
			upd(f[i][j][1], f[i-1][j-1][1]+w[i]*(10-a[i]-1));
			if (a[i]) upd(f[i][j][1], f[i-1][j-1][0]+w[i]*(10-a[i]));
		}
	write(f[lim][k][0]),putchar('\n');
}

signed main() {
	w[1] = 1;
	for (int i = 2; i <= lim; ++i) w[i] = w[i-1]*10;
	int t = read();
	while (t--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

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: 3812kb

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
1000000000000000042420637374017961984
1000000000000000000

result:

wrong answer 20th lines differ - expected: '99999999999999999900000000000000000', found: '1000000000000000042420637374017961984'