Rəqəmləri Təhmin Et#12229

Rəqəmləri Təhmin Et (Həll təhlili)

Problem Müəllifi:	KoasarTheJoyBoy
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Problem hər bir tək rəqəmə bölünmə tələb edildiyi üçün $n \equiv 0 (mod 315)$ n \equiv 0 (\bmod 315) tələb etməyə bərabərdir, çünki $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. Cavabı soldan sağa doğru dərinlikdən ilk axtarış (DFS) ilə $i = 0, 1, 2, ..., n - 1$ i=0,1,2,...,n-1 mövqeləri üzərində qururuq, cari qalıq $rem=(prefix mod 315)$ ilə birlikdə.

Hər $i$ -də biz $d$ rəqəmlərini artan sırada sınaqdan keçiririk; $n > 1$ n>1 olduqda $i = 0$ i=0-da sıfırları atlayırıq, son rəqəmi ${0, 5}$ -ə məcbur edirik ki, $mod 5 = 0$ \bmod 5=0 şərtini ödəsin və $s [i]$ -dəki hər hansı sabit rəqəmlə uyğunlaşırıq.

$rem \to (rem \cdot 10 + d) mod 315$ \text{rem} \rightarrow (\text{rem} \cdot 10+d) \bmod 315-i yeniləyirik və rekursiyanı çağırırıq. $i = n$ i=n və $rem = 0$ \text{rem}=0 olduqda, leksik olaraq ən kiçik etibarlı ədədi qurmuşuq. Eksponensial artımı qarşısını almaq üçün, hər $(i, rem)$ -in ən çox bir dəfə ziyarət edilməsi üçün boolean cədvəlində $used [i] [rem]$ \text{used}[i][\text{rem}] uğursuz vəziyyətləri xatırlayırıq. Bu DFS+memorization $O (n \cdot 315 \cdot 10) = O (n)$ \mathcal{O}(n \cdot 315 \cdot 10)=\mathcal{O}(n) test başına işləyir, $\sum ∣ s ∣ \leq 5000$ \sum |s| \le 5000-i rahatlıqla idarə edir.

#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++

Komplekslik $O (n)$