QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260073#6300. Best Carry Player 2extreme1228WA 1ms3388kbC++202.0kb2023-11-21 19:42:212023-11-21 19:42:22

Judging History

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

  • [2023-11-21 19:42:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3388kb
  • [2023-11-21 19:42:21]
  • 提交

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'