JAG Practice Contest for ACM-ICPC Asia Regional 2015 B - Change a Password

問題

jag2015autumn.contest.atcoder.jp

解法

N! 通りの全探索をするだけです。

ll calc(const string& s, const string& t) {
    int n = s.size();
    ll p = 1;
    for (int i = 0; i < n; i++) p *= 10;
    ll S = stoll(s), T = stoll(t);
    ll tmp = abs(S-T);
    return min(tmp, p-tmp);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int N = S.size();
    vector<int> perm(10);
    ll a = 1ll<<55, diff = -1;
    string ans;
    for (int i = 0; i < 10; i++) perm[i] = i;
    do {
        string tmp;
        for (int i = 0; i < N; i++) tmp += (char)('0'+perm[i]);
        ll d = calc(S, tmp);
        if (diff < d) {
            diff = d;
            ll t = stoll(tmp);
            ans = tmp;
            a = t;
        } else if (diff == d) {
            ll t = stoll(tmp);
            if (t < a) {
                ans = tmp;
                a = t;
            }
        }
    } while (next_permutation(perm.begin(), perm.end()));
    cout << ans << endl;
    return 0;
}