QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#690876 | #6300. Best Carry Player 2 | Idtwtei | WA | 1ms | 3812kb | C++14 | 1.4kb | 2024-10-31 07:18:53 | 2024-10-31 07:18:53 |
Judging History
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'