Codeforces Round #221 (Div. 1) A. Divisible by Seven

問題

codeforces.com

解法

1, 6, 8, 9 を適当に並び替えると, 7 で割った余りが 0, 1, ..., 6 のいずれにもなりえます。

ということで, 0, 1, 6, 8, 9 以外をとりあえず並べて, 1, 6, 8, 9 を全体の数が 7 の倍数になるように並べます。最後に, 0 を並べて終了です。

解法わかっても 1, 6, 8, 9 に必然性を感じないところがうーん。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> cnt(10);
    for (int i = 0; i < n; i++) cnt[s[i]-'0']++;
    string ans;
    int rest = 0;
    for (int i = 1; i < 10; i++) {
        if (i == 1 || i == 6 || i == 8 || i == 9) {
            for (int j = 0; j < cnt[i]-1; j++) {
                ans += (char)('0'+i);
                rest = (10*rest+i)%7;
            }
        } else {
            for (int j = 0; j < cnt[i]; j++) {
                ans += (char)('0'+i);
                rest = (10*rest+i)%7;
            }
        }
    }
    rest = (10000*rest)%7;
    vector<int> v = {1, 6, 8, 9};
    do {
        int tmp = 0;
        for (int i = 0; i < 4; i++) {
            tmp = (tmp*10+v[i])%7;
        }
        if ((tmp+rest)%7 == 0) {
            for (int i = 0; i < 4; i++) {
                ans += (char)('0'+v[i]);
            }
            break;
        }
    } while (next_permutation(v.begin(), v.end()));
    for (int i = 0; i < cnt[0]; i++) ans += '0';
    cout << ans << endl;
    return 0;
}