QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260073 | #6300. Best Carry Player 2 | extreme1228 | WA | 1ms | 3388kb | C++20 | 2.0kb | 2023-11-21 19:42:21 | 2023-11-21 19:42:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;
const int maxn = 50;
ll dp[maxn][maxn][2];//dp[i][j][0/1]表示从低位开始到第i位,以及进位过j次且当前位是否向前进位情况下的最小y值
ll p_10[maxn];
void solve()
{
ll x,k;
cin>>x>>k;
if(k == 0){
//k == 0特判
ll ans = 1;
while(x%10 == 9){
x/=10;
ans*=10;
}
cout<<ans<<"\n";
return;
}
//提前对x末尾的0做出预处理,防止爆long long
int cnt_0 = 0;
while(x%10 == 0){
cnt_0++;
x/=10;
}
//x存入数组
vector<int>num(50,0);
int pos = 0;
while(x){
num[++pos] = x%10;
x/=10;
}
for(int i=0;i<=20;i++)
for(int j=0;j<=20;j++)
for(int k=0;k<=1;k++){
dp[i][j][k] = INF;
}
dp[0][0][0] = 0;
for(int i=1;i<=18;i++)
for(int j=0;j<=i;j++)
{
if(num[i] == 9){
dp[i][j][0] = min(dp[i][j][0],dp[i-1][j][0]);
if(j>=1)dp[i][j][1] = min(dp[i][j][1],dp[i-1][j-1][1]);
if(j>=1)dp[i][j][1] = min(dp[i][j][1],dp[i-1][j-1][0] + p_10[i-1]);
}
else{
dp[i][j][0] = min(dp[i][j][0],min(dp[i-1][j][0],dp[i-1][j][1]));
if(j>=1)dp[i][j][1] = min(dp[i][j][1],dp[i-1][j-1][0] + p_10[i-1]*(10 - num[i]));
if(j>=1)dp[i][j][1] = min(dp[i][j][1],dp[i-1][j-1][1] + p_10[i-1]*(9-num[i]));
}
}
// cerr<<dp[2][1][1]<<"\n";
cout<<min(dp[18][k][0],dp[18][k][1]);
while(cnt_0--)cout<<"0";
cout<<"\n";
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin>>t;
p_10[0] = 1;
for(int i=1;i<=18;i++){
p_10[i] = p_10[i-1]*10;
}
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3388kb
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: 3384kb
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 10000000000 9999910000 9999901000 9999900100 9999900010 9999900001 9000009999900001 99000009999900001 999000009999900001 99999999999999999900000000000000000 1000000000000000000
result:
wrong answer 11th lines differ - expected: '10000000001', found: '10000000000'