Codeforces Round #206 (Div. 1) E. Lucky Number Representation

問題

codeforces.com

解法

桁 DP するだけです。dp[keta][carry] = (keta 目の桁で, 繰り上がりが carry であるような場合に, 和を N にするような 6 つの数字が存在するか)みたいなことをやります。

各状態では, 6 つの数字を 0, 4, 7 のどれにするかを 3^6 個ぐらい調べれば良いです。

int digit[3] = {0, 4, 7};
bool done[20][10];
bool ok;

void dfs(int keta, int carry, vector<ll>& v, ll tar) {
    if (ok || done[keta][carry]) return;
    done[keta][carry] = true;
    if (keta >= 18) {
        ll sum = 0;
        for (ll el : v) sum += el;
        if (sum == tar) {
            ok = true;
            for (ll el : v) cout << el << " ";
            cout << endl;
        }
        return;
    }
    ll p = 1;
    for (int i = 0; i < keta; i++) p *= 10;
    for (int i = 0; i < 3; i++) for (int j = i; j < 3; j++) for (int k = j; k < 3; k++) {
        for (int l = k; l < 3; l++) for (int m = l; m < 3; m++) for (int n = m; n < 3; n++) {
            int sum = digit[i] + digit[j] + digit[k] + digit[l] + digit[m] + digit[n] + carry;
            if ((sum%10) != ((tar/p)%10)) continue;
            int nc = sum/10;
            vector<ll> nv(6);
            v[0] += digit[i] * p;
            v[1] += digit[j] * p;
            v[2] += digit[k] * p;
            v[3] += digit[l] * p;
            v[4] += digit[m] * p;
            v[5] += digit[n] * p;
            dfs(keta+1, nc, v, tar);
            if (ok) return;
            v[0] -= digit[i] * p;
            v[1] -= digit[j] * p;
            v[2] -= digit[k] * p;
            v[3] -= digit[l] * p;
            v[4] -= digit[m] * p;
            v[5] -= digit[n] * p;
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        ll N;
        cin >> N;
        vector<ll> v(6, 0);
        ok = false;
        memset(done, false, sizeof(done));
        dfs(0, 0, v, N);
        if (!ok) cout << -1 << endl;
    }
    return 0;
}