Submission #1240951

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
#define INF 1e18
ll A; int K;
//-----------------------------------------------------------------------------------
ll dp[20][1 << 10][2];
ll solve() {
    rep(i, 0, 20) rep(j, 0, 1 << 10) {
        dp[i][j][0] = -INF;
        dp[i][j][1] = INF;
    }

    string s = to_string(A);
    int n = s.length();

    dp[0][0][0] = 0;
    ll x = 0;
    rep(i, 0, n) {
        x = x * 10 + s[i] - '0';
        rep(ma, 0, 1 << 10) rep(f, 0, 2) {
            int cnt = 0;
            rep(j, 0, 10) if (ma & (1 << j)) cnt++;

            rep(j, 0, 10) {
                ll ne = dp[i][ma][f] * 10 + j;

                if (cnt == K && (ma & (1 << j)) == 0) continue;

                if (ne < x) {
                    dp[i + 1][ma | (1 << j)][0] = max(dp[i + 1][ma | (1 << j)][0], ne);
                }
                else {
                    dp[i + 1][ma | (1 << j)][1] = min(dp[i + 1][ma | (1 << j)][1], ne);
                }
            }
        }
    }

    ll ans = INF;
    rep(i, 0, n + 1) rep(ma, 0, 1 << 10) rep(f, 0, 2) ans = min(ans, abs(A - dp[i][ma][f]));
    return ans;
}
//-----------------------------------------------------------------------------------
int main() {
    cin >> A >> K;

    cout << solve() << endl;
}

Submission Info

Judge Result