Introduction à l'Épreuve NOIP2021

Le problème t1 de NOIP2021 modifie les règles d'un jeu de reportage. La règle ajoutée est que si un nombre x contient le chiffre 7 dans sa représentation décimale, alors x et tous ses multiples (yx, où y est un entier positif) ne doivent pas être prononcés. L'objectif est de déterminer le prochain nombre valide après un nombre donné.

Approche Préliminaire par Filtrage

Pour résoudre ce problème, on peut précalculer tous les nombres contenant au moins un chiffre 7 jusqu'à une limite maximale. Ensuite, on marque tous ces nombres et leurs multiples comme invalides. Les nombres restants forment la séquence valide.

La méthode initiale utilise une approche similaire au crible d'Ératosthène. On initialise un tableau valide à vrai pour tous les indices. Puis, pour chaque nombre contenant un 7, on le marque comme faux et on marque également tous ses multiples. Finalement, on construit un tableau de réponses pour stocker le prochain nombre valide pour chaque index.

Implémentation en C++ avec Optimisation de Base

#include <iostream>
#include <vector>
using namespace std;

bool contientChiffreSept(int n) {
    while (n > 0) {
        if (n % 10 == 7) return true;
        n /= 10;
    }
    return false;
}

int main() {
    const int MAX_VAL = 10000000;
    vector<bool> estValide(MAX_VAL + 2, true);
    vector<int> nombresSept;

    // Identifier tous les nombres contenant le chiffre 7
    for (int i = 1; i <= MAX_VAL; ++i) {
        if (contientChiffreSept(i)) {
            nombresSept.push_back(i);
            estValide[i] = false;
        }
    }

    // Marquer tous les multiples des nombres identifiés
    for (int i = 1; i <= MAX_VAL; ++i) {
        for (int sept : nombresSept) {
            long long multiple = static_cast<long long>(i) * sept;
            if (multiple > MAX_VAL) break;
            estValide[multiple] = false;
        }
    }

    // Construire le tableau de réponses
    vector<int> prochainValide(MAX_VAL + 2, -1);
    int precedent = -1;
    for (int i = MAX_VAL + 1; i >= 1; --i) {
        if (estValide[i]) {
            prochainValide[i] = precedent;
            precedent = i;
        }
    }

    // Traitement des requêtes
    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        cout << prochainValide[x] << endl;
    }
    return 0;
}

Optimisation avec Filtrage à la Manière d'Euler

L'implémentation précédente peut entraîner des marquages multiples pour un même nombre. Une optimisation consiste à appliquer un filtrage similaire au crible d'Euler, où chaque nombre n'est marqué qu'une seule fois par le plus petit facteur premier qui le divise. Ici, on adapte l'idée pour les nombres contenant un 7.

Dans la boucle de marquage des multiples, on ajoute une condition pour arrêter la boucle interne lorsque i est dviisible par le nombre courant de nombresSept. Cela garantit que chaque multilpe est traité par le plus petit facteur possible, réduisant ainsi le nombre total d'opérations.

Code Optimisé

#include <iostream>
#include <vector>
using namespace std;

bool contientChiffreSept(int n) {
    while (n > 0) {
        if (n % 10 == 7) return true;
        n /= 10;
    }
    return false;
}

int main() {
    const int MAX_VAL = 10000000;
    vector<bool> estValide(MAX_VAL + 2, true);
    vector<int> nombresSept;

    for (int i = 1; i <= MAX_VAL; ++i) {
        if (contientChiffreSept(i)) {
            nombresSept.push_back(i);
            estValide[i] = false;
        }
    }

    // Filtrage optimisé avec arrêt précoce
    for (int i = 1; i <= MAX_VAL; ++i) {
        for (size_t j = 0; j < nombresSept.size(); ++j) {
            int sept = nombresSept[j];
            long long multiple = static_cast<long long>(i) * sept;
            if (multiple > MAX_VAL) break;
            estValide[multiple] = false;
            if (i % sept == 0) break; // Optimisation clé
        }
    }

    vector<int> prochainValide(MAX_VAL + 2, -1);
    int precedent = -1;
    for (int i = MAX_VAL + 1; i >= 1; --i) {
        if (estValide[i]) {
            prochainValide[i] = precedent;
            precedent = i;
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        cout << prochainValide[x] << endl;
    }
    return 0;
}

Considérations de Performance

L'utilisation d'entrées/sorties standards peut être lente pour de grands volumes de données. Dans des environnements de concours, il est recommandé d'utiliser des techniques d'E/S rapides, comme la lecture par blocs ou des fonctions personnalisées. Cependant, pour la clarté, cet exemple utilise les E/S standards.

La complexité temporelle dépend de la distribution des nombres contenant un 7. L'optimisation avec le crible d'Euler réduit significativement le nombre d'opérations en pratique, bien que la complexité théorique reste similaire dans le pire cas.