QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#286722#6300. Best Carry Player 2000226#WA 1ms3840kbC++172.0kb2023-12-18 14:28:272023-12-18 14:28:27

Judging History

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

  • [2023-12-18 14:28:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2023-12-18 14:28:27]
  • 提交

answer

#include <bits/stdc++.h>

#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define debug(...) fprintf (stderr, __VA_ARGS__)

using std :: cin;
using std :: cout;
using std :: endl;
using std :: cerr;
using i64 = long long;

const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline int add(int x, int y) { return mod(x + y - P); }
inline int dec(int x, int y) { return mod(x - y); }
inline int power(int x, int k) {
	int res = 1; if (k < 0) k += P - 1;
	while (k) { if (k & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; k >>= 1; }
	return res;
}

__int128 dp[22][22][2]; // 第几位 进位次数 当前位有没有进位
int s[22], top;
__int128 pw[24];
int K;

__int128 dfs (int now, int cnt, int o) {
	if (dp[now][cnt][o] != -1) return dp[now][cnt][o];
	if (now > 20) {
		if (cnt == K) return 0;
		return 1e20;
	}
	__int128 ans = 1e20;
	for (int i = 0; i <= 9; i ++) {
		int ok = (i + o + s[now]) >= 10;
		ans = std :: min (ans, dfs (now + 1, cnt + ok, ok) + i * pw[now - 1]);
	}
	return dp[now][cnt][o] = ans;
} 

void print (__int128 x) {
	if (x) {
		print (x / 10);
		cout << (int) (x % 10);
	}
}

void solve() {
	memset (dp, -1, sizeof (dp));
	i64 n;
	pw[0] = 1;
	for (int i = 1; i <= 22; i ++) pw[i] = pw[i - 1] * 10;
	cin >> n >> K;

	if (K == 0) {
		__int128 now = 1;
		for (int i = 1; i <= 20; i ++) {
			if (n / now % 10 != 9) {
				print (now);
				cout << endl;
				return ;
			}
			now *= 10;
		}
		assert (0);
		return ;
	}

	top = 0;
	while (n) s[++ top] = n % 10, n /= 10;
	s[top + 1] = s[top + 2] = 0;
	__int128 ans = dfs (1, 0, 0);
	if (ans > 1e20) {
		cout << -1 << endl;
	} else print (dfs (1, 0, 0));
	cout << endl;
}

int main() {
	std :: ios :: sync_with_stdio(false);
	int Case; cin >> Case;
	while (Case --) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

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

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

result:

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