Introduction à la programmation compétitive en C++ et gestion d'entrée sortie (E/S)

La programmation compétitive combine deux thèmes : la conception d'algorithmes et la mise en œuvre d'algorithmes

Le cœur de la programmation compétitive consiste à inventer des algorithmes efficaces qui résolvent des problèmes de calcul bien définis. La conception d'algorithmes nécessite des compétences en résolution de problèmes et en mathématiques. Souvent, une solution à un problème est une combinaison de méthodes bien connues et de nouvelles idées.

Dans la programmation compétitive, les solutions aux problèmes sont évaluées en testant un algorithme implémenté à l'aide d'un ensemble de cas de test. Ainsi, après avoir proposé un algorithme qui résout le problème, l'étape suivante consiste à l'implémenter correctement, ce qui nécessite de bonnes compétences en programmation. La programmation compétitive diffère grandement de l'ingénierie logicielle traditionnelle : les programmes sont courts (généralement au plus quelques centaines de lignes), ils doivent être écrits rapidement.

Un problème dans une compétition de programmation contient généralement les éléments suivants :

•  Description du problème. Habituellement, les problèmes les plus faciles sont écrits pour tromper les candidats et présentés comme difficiles, par exemple en ajoutant des « informations supplémentaires » pour créer une diversion. Les candidats doivent être en mesure de filtrer ces détails sans importance et de se concentrer sur les éléments essentiels
•  Description des entrées et sorties. Cette section décrit comment l'entrée est formatée et comment vous devez formater votre sortie. Cette partie est généralement écrite de manière formelle. Un bon problème doit avoir des contraintes d'entrée claires car le même problème peut être résolu avec différents algorithmes pour différentes contraintes d'entrée
•  Exemple d'entrée et exemple de sortie. Les auteurs de problèmes ne fournissent généralement que des cas de test triviaux aux candidats. L'exemple d'entrée/sortie est destiné aux candidats pour vérifier leur compréhension de base du problème et pour vérifier si leur code peut analyser l'entrée donnée en utilisant le format d'entrée donné et produire la sortie correcte en utilisant le format de sortie donné. Ne soumettez pas votre code au juge s'il ne passe même pas l'exemple d'entrée/sortie donnée.
•  Conseils ou notes. Dans certains cas, les auteurs du problème peuvent laisser des indices ou ajouter des notes pour décrire plus en détail le problème.

Un modèle de code C++ typique pour la programmation compétitive ressemble à ceci :

#include <bits/stdc++.h>

using namespace std;

int main() {
    // solution du problème

    return 0;
}
        

La ligne #include au début du code est une fonctionnalité du compilateur g++ qui nous permet d'inclure l'intégralité de la bibliothèque standard. Ainsi, il n'est pas nécessaire d'inclure séparément des bibliothèques telles que iostream, vector et algorithm, mais elles sont plutôt disponibles automatiquement

La ligne using déclare que les classes et fonctions de la bibliothèque standard peuvent être utilisées directement dans le code. Sans la ligne using, nous aurions à écrire, par exemple, std::cout, mais maintenant il suffit d'écrire cout.

Dans la plupart des compétitions, des flux standard sont utilisés pour lire les entrées et écrire les sorties. En C++, les flux standard sont cin pour l'entrée et cout pour la sortie. Les fonctions C, telles que scanf et printf, peuvent également être utilisées.

Il est souvent recommandé d'utiliser scanf/printf au lieu de cin/cout pour une entrée et une sortie rapides. Cependant, vous pouvez toujours utiliser cin/cout et atteindre la même vitesse que scanf/printf en incluant les deux lignes suivantes dans votre fonction main() :

ios_base::sync_with_stdio(false);
cin.tie(NULL);
        

Il est recommandé d'utiliser "\n" ; au lieu de endl;. endl est plus lente car provoque toujours un vidage de flux, ce qui est généralement inutile.

Ainsi, votre modèle de code pour la programmation compétitive pourrait ressembler à ceci :

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // solution du problème

    return 0;
}
        

Cas de test multiples

Dans un problème de programmation compétitive, l'exactitude de votre code est généralement déterminée en exécutant votre code sur plusieurs cas de test. Plutôt que d'utiliser de nombreux fichiers de cas de test individuels, les problèmes de programmation compétitive modernes utilisent généralement un fichier de cas de test avec plusieurs cas de test inclus.

Dans cette section, nous utilisons un problème très simple comme exemple de problème à plusieurs cas de test : étant donné deux nombres entiers sur une ligne, affichez leur somme sur une ligne. Nous allons illustrer trois formats d'entrée/sortie possibles :

•  Le nombre de cas de test est indiqué dans la première ligne de l'entrée.
•  Les cas de test multiples se terminent par des valeurs spéciales (généralement des zéros).
•  Les cas test multiple sont terminés par le signal EOF (fin de fichier).

Exemple 1 :

4
1 2
5 7
6 3
10 5
                            

3
12
9
15
                            

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a,b,nb;
    scanf("%d",&nb); // nombre de cas (première ligne)
    // ou bien simplement cin>>nb;

    while(nb--){ // répéter jusqu'à ce que nb=0

        scanf("%d %d",&a,&b); // lire une ligne de cas
        // ou bien cin>>a>>b;

        printf("%d\n",a+b); // afficher la sortie (résultat)
        // ou bien cout<<a+b<<"\n";
    }

    return 0;
}
        

Exemple 2 :

1 2
5 7
6 3
0 0
                            

3
12
9
                            

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a,b;
    
    // s'arrêter quand les deux entiers valent 0
    while (cin>>a>>b, (a || b)){
        cout<<a+b<<"\n";
    }

    return 0;
}
        

Nombre variable d'entrées

Modifions légèrement le problème simple ci-dessus. Pour chaque cas de test (chaque ligne d'entrée), on nous donne maintenant un entier k (\(k \ge 1\)), suivi de k entiers. Notre tâche est maintenant de sortir la somme de ces k entiers.

Exemple 3 :

1 5
2 14 15
4 1 5 8 7
3 2 5 4
0
                            

5
29
21
11
                            

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int k,a,s;
    
    // s'arrêter quand on n'a pas une valeur pour k ou k=0
    while (cin>>k, k){
        s=0;
        while(k--){cin>>a;s+=a;}
        cout<<s<<"\n";
    }

    return 0;
}
        

Exemple 4 :

L'entrée est constituée d'une liste d'entiers i, la sortie est la somme de ces nombres.

2 5 4 3 7 9 15

45

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a,s;
    s=0;
    // s'arrêter quand on n'a pas une valeur (fin de la liste)
    while (cin>>a){
        s+=a;
    }
    cout<<s;

    return 0;
}