Chỉ là phép nhân

Điểm: 1,82 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

MTA

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

~2~ bạn ~A~ và ~B~ chơi ~1~ trò như sau:

~A~ nghĩ ra ~1~ số ~x~, có ~k~ chữ số, tổng các chữ số của ~x = S~ và giữ bí mật số ~x~ đó, ~B~ nghĩ ra ~1~ số ~D~ có ~1~ chữ số, và nói cho ~A~. ~A~ tính kết quả của ~x \times d~ và thông báo cho ~B~ số ~P~ là tổng các chữ số của kết quả đó và thách đố ~B~ tìm ra số ~x~ ban đầu. Help ~B~

Input

~1~ dòng gồm ~4~ số: ~k~, ~S~, ~P~, ~D~

Output

In ra ~x~, nếu có nhiều kết quả in ra kết quả nhỏ nhất, nếu ko có kết quả nào in ra ~- 1~.

Giới hạn

~1 \le k \le 100~;

Sample Input

2 9 9 5

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

chuthang050520008 đã bình luận lúc 19, Tháng 10, 2025, 15:14

include <bits/stdc++.h>

using namespace std;

string findx(int k, int S, int P, int D) { const int MAXP = 1000; vector<unorderedmap<long long, bitset<MAXP+1>>> dp(k + 1); dp[0][(0LL << 10) | S].set(0);

for (int pos = 0; pos < k; pos++) {
    unordered_map&lt;long long, bitset<MAXP+1>> nxt;
    for (auto &[key, mask] : dp[pos]) {
        int carry = key >> 10;
        int rem = key & 1023;
        for (int d = 0; d <= 9; d++) {
            if (rem < d) break;
            if (pos == k - 1 && d == 0) continue;
            int prod = D * d + carry;
            int res = prod % 10;
            int newc = prod / 10;
            int newrem = rem - d;
            long long nkey = ((long long)newc << 10) | newrem;
            bitset<MAXP+1> shifted = (mask << res);
            nxt[nkey] |= shifted;
        }
    }
    dp[pos+1].swap(nxt);
}

vector<int> candidates;
for (auto &[key, mask] : dp[k]) {
    int carry = key >> 10;
    int rem = key & 1023;
    if (rem != 0) continue;
    int sdc = 0;
    for (int t = carry; t; t /= 10) sdc += t % 10;
    int residual = P - sdc;
    if (residual >= 0 && residual <= MAXP && mask[residual])
        candidates.push_back(carry);
}

if (candidates.empty()) return "-1";
sort(candidates.begin(), candidates.end());

auto reconstruct = [&](int final_carry) -> vector<int> {
    int target_residual = P;
    for (int t = final_carry; t; t /= 10) target_residual -= t % 10;
    pair<int,int> target_state = {final_carry, 0};
    vector<int> digits(k, 0);

    for (int pos = k - 1; pos >= 0; pos--) {
        bool found = false;
        int d_start = (pos == k - 1 ? 1 : 0);
        for (int d = d_start; d <= 9 && !found; d++) {
            int prev_rem = target_state.second + d;
            for (int carry_prev = 0; carry_prev <= 900; carry_prev++) {
                int prod = D * d + carry_prev;
                if (prod / 10 != target_state.first) continue;
                int res = prod % 10;
                long long pkey = ((long long)carry_prev << 10) | prev_rem;
                if (!dp[pos].count(pkey)) continue;
                const bitset<MAXP+1> &mask_prev = dp[pos].at(pkey);
                int need = target_residual - res;
                if (need < 0 || need > MAXP) continue;
                if (mask_prev[need]) {
                    digits[pos] = d;
                    target_residual = need;
                    target_state = {carry_prev, prev_rem};
                    found = true;
                    break;
                }
            }
        }
        if (!found) return vector<int>();
    }
    if (target_residual == 0 && target_state.first == 0 && target_state.second == S)
        return digits;
    return vector<int>();
};

string best = "";
for (int c : candidates) {
    auto digits = reconstruct(c);
    if (digits.empty()) continue;
    string s = "";
    for (int i = k - 1; i >= 0; i--) s += char('0' + digits[i]);
    if (best.empty() || s.size() < best.size() || (s.size() == best.size() && s < best))
        best = s;
}
return best.empty() ? "-1" : best;

}

int main() { ios::syncwithstdio(false); cin.tie(nullptr); int k, S, P, D; cin >> k >> S >> P >> D; cout << find_x(k, S, P, D) << "\n"; }

-4

danglebinhnguyen2014 đã bình luận lúc 4, Tháng 12, 2024, 4:56

Đừng nhấn nữa mà

Bài khó quá