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 leur implémentation. L'objectif est d'inventer des algorithmes efficaces qui résolvent des problèmes de calcul bien définis, en combinant des méthodes connues et de nouvelles idées. Les solutions sont évaluées en les testant sur un ensemble de cas de test.

Structure d'un problème de compétition

Un problème de compétition contient généralement quatre éléments :

• Description du problème — les problèmes faciles sont parfois présentés comme difficiles avec des « informations supplémentaires » distracteurs. Il faut filtrer l'essentiel.
• Description des entrées et sorties — format précis et formel. Les contraintes d'entrée sont cruciales car elles déterminent quel algorithme est applicable.
• Exemples d'entrée/sortie — cas de test triviaux pour vérifier la compréhension du problème et valider le parsing. Ne jamais soumettre un code qui ne passe pas ces exemples.
• Conseils ou notes — indices optionnels laissés par les auteurs pour clarifier le problème.

Template de code C++

Un template typique pour la programmation compétitive en C++ :

#include <bits/stdc++.h>
using namespace std;

int main() {
    // solution du problème
    return 0;
}

Entrée et sortie rapides

En compétition, la vitesse d'I/O peut être critique. On peut utiliser scanf/printf (fonctions C) ou cin/cout avec les deux optimisations suivantes :

#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

Les problèmes modernes regroupent tous les cas de test dans un seul fichier d'entrée. Trois formats d'entrée sont courants.

Format 1 — Nombre de cas indiqué en première ligne

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;
    cin >> nb;              // lire le nombre de cas

    while (nb--) {          // répéter nb fois
        cin >> a >> b;
        cout << a + b << "\n";
    }
    return 0;
}

Format 2 — Fin marquée par des valeurs sentinelles (ex. : 0 0)

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 a == 0 ET b == 0
    while (cin >> a >> b, (a || b)) {
        cout << a + b << "\n";
    }
    return 0;
}

Format 3 — Nombre variable d'entiers par ligne

Pour chaque cas, on lit d'abord un entier k (nombre d'éléments qui suivent), puis k entiers dont on calcule la somme. La valeur 0 pour k signale la fin.

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 k == 0
    while (cin >> k, k) {
        s = 0;
        while (k--) { cin >> a; s += a; }
        cout << s << "\n";
    }
    return 0;
}

Format 4 — Lecture jusqu'à EOF (fin de fichier)

Lorsqu'aucun séparateur de cas n'est spécifié, on lit les entiers jusqu'à la fin du fichier.

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 = 0;
    // cin >> a retourne false à la fin du fichier
    while (cin >> a) {
        s += a;
    }
    cout << s;
    return 0;
}