Devinez Les Chiffres#12229

Devinez Les Chiffres (Corrigé)

Auteur du problème:	KoasarTheJoyBoy
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution Le truc est que le problème exige que la divisibilité par chaque chiffre impair présent est équivalente à exiger $n \equiv 0 (mod 315)$ n \equiv 0 (\bmod 315), puisque $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. Nous construisons la réponse de gauche à droite par une recherche en profondeur (DFS) sur les positions $i = 0, 1, 2, ..., n - 1$ i=0,1,2,...,n-1, en portant le reste actuel $rem=(prefix mod 315)$ .

À chaque $i$ , nous essayons les chiffres $d$ dans l'ordre croissant ; en sautant les zéros à $i = 0$ i=0 lorsque $n > 1$ n>1, en forçant le dernier chiffre à ${0, 5}$ pour satisfaire $mod 5 = 0$ \bmod 5=0, et en faisant correspondre tout chiffre fixe dans $s [i]$ .

Nous mettons à jour $rem \to (rem \cdot 10 + d) mod 315$ \text{rem} \rightarrow (\text{rem} \cdot 10+d) \bmod 315 et appelons la récursion. Dès que $i = n$ i=n et $rem = 0$ \text{rem}=0, nous avons construit le plus petit nombre valide lexicographiquement. Pour éviter une explosion exponentielle, nous nous souvenons des états échoués dans une table booléenne $used [i] [rem]$ \text{used}[i][\text{rem}] afin que chaque $(i, rem)$ soit visité au plus une fois. Cette DFS+mémoïsation fonctionne en $O (n \cdot 315 \cdot 10) = O (n)$ \mathcal{O}(n \cdot 315 \cdot 10)=\mathcal{O}(n) par test, gérant confortablement $\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++

Complexité $O (n)$