Adivina Los Dígitos (Editorial)

Solución El truco es que el problema requiere divisibilidad por cada dígito impar presente, lo que equivale a requerir n \equiv 0 (\bmod 315), ya que \text{lcm}(1,3,5,7,9)=3^2 \cdot 5 \cdot 7=315. Construimos la respuesta de izquierda a derecha mediante una búsqueda en profundidad (DFS) sobre las posiciones i=0,1,2,...,n-1, llevando consigo el resto actual $\text{rem=(prefijo mod 315)}$.

En cada $i$ probamos dígitos $d$ en orden ascendente; omitiendo ceros en i=0 cuando n>1, forzando el último dígito en $\{0,5\}$ para satisfacer \bmod 5=0, y coincidiendo con cualquier dígito fijo en $s[i]$.

Actualizamos \text{rem} \rightarrow (\text{rem} \cdot 10+d) \bmod 315 y llamamos a la recursión. Tan pronto como i=n y \text{rem}=0, hemos construido el número válido más pequeño lexicográficamente. Para evitar un crecimiento exponencial, recordamos los estados fallidos en una tabla booleana \text{used}[i][\text{rem}] para que cada $(i,\text{rem})$ sea visitado como máximo una vez. Este DFS+memorización se ejecuta en \mathcal{O}(n \cdot 315 \cdot 10)=\mathcal{O}(n) por prueba, manejando cómodamente \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;
}

Complejidad $\mathcal{O}(n)$