Вгадай Цифри#12229

Вгадай Цифри (Розбір)

Автор проблеми:	KoasarTheJoyBoy
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Розв'язок Суть у тому, що вимога ділитися на кожну непарну цифру еквівалентна вимозі $n \equiv 0 (mod 315)$ n \equiv 0 (\bmod 315), оскільки $lcm (1, 3, 5, 7, 9) = 3^{2} \cdot 5 \cdot 7 = 315$ \text{lcm}(1,3,5,7,9)=3^2 \cdot 5 \cdot 7=315. Ми будуємо відповідь зліва направо за допомогою пошуку в глибину (DFS) по позиціях $i = 0, 1, 2, ..., n - 1$ i=0,1,2,...,n-1, передаючи поточний залишок $rem=(prefix mod 315)$ .

На кожному $i$ ми пробуємо цифри $d$ у порядку зростання; пропускаючи нулі на $i = 0$ i=0, коли $n > 1$ n>1, змушуючи останню цифру бути в ${0, 5}$ , щоб задовольнити $mod 5 = 0$ \bmod 5=0, і підбираючи будь-яку фіксовану цифру в $s [i]$ .

Ми оновлюємо $rem \to (rem \cdot 10 + d) mod 315$ \text{rem} \rightarrow (\text{rem} \cdot 10+d) \bmod 315 і викликаємо рекурсію. Як тільки $i = n$ i=n і $rem = 0$ \text{rem}=0, ми побудували лексикографічно найменше допустиме число. Щоб уникнути експоненційного зростання, ми запам'ятовуємо невдалі стани в булевій таблиці $used [i] [rem]$ \text{used}[i][\text{rem}], щоб кожен $(i, rem)$ відвідувався не більше одного разу. Цей DFS+запам'ятовування працює за $O (n \cdot 315 \cdot 10) = O (n)$ \mathcal{O}(n \cdot 315 \cdot 10)=\mathcal{O}(n) на тест, що комфортно обробляє $\sum ∣ s ∣ \leq 5000$ \sum |s| \le 5000.

#include <bits/stdc++.h>
using namespace std;

int n;
string s, ans;
static bool used[5005][315];

bool dfs(int i, int rem) {
    if (i == n)
        return rem == 0;
    if (used[i][rem])
        return false;
    used[i][rem] = true;
    bool last = (i == n - 1);
    for (int d = 0; d < 10; ++d) {
        if (s[i] != '?' && s[i] - '0' != d) continue;
        if (i == 0 && n > 1 && d == 0) continue;
        if (last && d % 5 != 0) continue;
        int nrem = (rem * 10 + d) % 315;
        ans.push_back('0' + d);
        if (dfs(i + 1, nrem))
            return true;
        ans.pop_back();
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        cin >> s;
        n = s.size();
        ans.clear();
        for (int i = 0; i <= n; ++i)
            for (int r = 0; r < 315; ++r)
                used[i][r] = false;
        if (dfs(0, 0))
            cout << ans << '\n';
        else
            cout << -1 << '\n';
    }
    return 0;
}

C++

Складність $O (n)$