Guess The Digits#12229

Guess The Digits (Editorial)

Problem Author:	KoasarTheJoyBoy
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution The trick is that the problem is requiring divisibility by each odd digit present is equivalent to requiring $n \equiv 0 (mod 315)$ n \equiv 0 (\bmod 315), since $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. We build the answer left to right by a depth-first search (DFS) over positions $i = 0, 1, 2, ..., n - 1$ i=0,1,2,...,n-1, carrying along the current remainder $rem=(prefix mod 315)$ .

At each $i$ we try digits $d$ in ascending order ; skipping zeros at $i = 0$ i=0 when $n > 1$ n>1, forcing the last digit into ${0, 5}$ to satisfy $mod 5 = 0$ \bmod 5=0, and matching any fixed digit in $s [i]$ .

We update $rem \to (rem \cdot 10 + d) mod 315$ \text{rem} \rightarrow (\text{rem} \cdot 10+d) \bmod 315 and call the recursion. As soon as $i = n$ i=n and $rem = 0$ \text{rem}=0, we've constructed the lexicographically smallest valid number. To avoid exponential blowup, we remember failed states in a boolean table $used [i] [rem]$ \text{used}[i][\text{rem}] so each $(i, rem)$ is visited at most once. This DFS+memorization runs in $O (n \cdot 315 \cdot 10) = O (n)$ \mathcal{O}(n \cdot 315 \cdot 10)=\mathcal{O}(n) per test, comfortably handling $\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++

Complexity $O (n)$