1
Initiation à la résolution des
problèmes
Responsables
Dr. Mariam Lahami
Dr. Afef Mdhaffar
2
3
Objectifs
• Améliorer vos compétences en programmation et
apprendre les bons reflexes
• S’entraîner à résoudre divers types de problèmes
(issus de compétitions de programmation)
• Promouvoir la créativité, le travail d’équipe, la
pensée critique, l’innovation dans la résolution de
problèmes et la programmation efficace
4
Concours de programmation
• Une bataille de cerveaux !
▫ Chaque équipe (3 ou 2 étudiants de la même institution) doit
proposer des solutions optimales pour des problèmes
algorithmiques en X heures.
▫ Le nombre d’heures X varie selon le concours
à Permettre aux étudiants de:
à tester leur capacité
à donner le meilleur d’eux
à Faire preuve d’organisation et d’habileté
au codage
5
Concours de programmation
• Principe : ces équipes dotées d’une seule machine,
doivent résoudre divers problèmes en écrivant, pour
chacun, un programme dans un langage de
programmation au choix.
• L'équipe gagnante est celle qui résout le plus grand
nombre de problèmes, tout en prenant le moins de
temps
6
Concours de programmation les plus
célèbres
• Plusieurs compétitions internationales :
▫ International Olympiad in informatics (IOI)
▫ International Collegiate Programming Contest de
ACM (ICPC).
▫ Arab Collegiate Programming Contest de ACM
(ACPC).
▫ IEEE Xtreme de IEEE
▫ Code Jam de Google
• Plusieurs compétitions nationales :
▫ Tunisian Collegiate Programming Contest de ACM
(TCPC).
Page FB : [Link]
7
Concours de programmation les plus
célèbres
8
Concours de programmation national
TCPC
9
Concours de programmation national
TCPC
10
Concours de programmation national
ACM : Qualification de la région de Sfax au TCPC
11
Concours de programmation
Hello World V1.0 à ENIS Mai 2019
12
Concours de programmation
Tournois à la Foire de Sfax
13
Concours de programmation
Tournois à ENIS
14
Objectif
15
Compétitions en ligne
• Pour s’entrainer, vous pouvez suivre des
compétitions en ligne
▫ Kattis : [Link]
▫ Codeforces: [Link]
▫ CodeChef: [Link]
▫ Codin’Game : [Link]
▫ HackerRank : [Link]
▫ TopCoder : [Link]
▫ Etc.
16
Codeforces
• Site très utilisé pour s’entrainer à la
programmation compétitive
▫ Utilisé par la communauté de ICPC
17
Codeforces
• Fournit des problèmes de différents niveaux de
difficultés
• Différents langages de programmation peuvent être
utilisés pour résoudre ces problèmes
Le plus facile
Le plus difficile
18
Codeforces
Accueil
19
Codeforces
Accueil
20
Codeforces
Accueil
21
Codeforces
Soumission
Choisir le langage
de programmation
Mettre votre code ICI
22
Codeforces
Verdict
Types de verdicts
23
Codeforces
Verdict
• Différents types de verdicts
24
Codeforces
Score
• Le score est calculé en se basant sur:
▫ le temps requis pour résoudre un problème
▫ La pénalité (20 min) pour chaque soumission
rejetée ScoreBoard
• Par exemple :
▫ Un problème est résolu à la minute
15 après 2 essais erronés
Le score = 15 +2*20=55
25
Codeforces
Input&Output
26
Quelques recommandations: I/O
Code en langage C/C++ Code en langage C++
• Saisie des entrées • Saisie des entrées
▫ Cas de deux variables ▫ Cas de deux variables
scanf(‘’%d %d’’,&a,&b) cin>>a>>b;
▫ Cas d’un tableau de ▫ Cas d’un tableau de
valeurs valeurs
for(int i=0;i<n;i++) for(int i=0;i<n;i++)
scanf(‘’%d’’,&ai[i]); cin>>ai[i];
• Affichage des résultats
• Affichage des résultats
▫ cout<<res<<endl;
▫ printf(‘’%d’’,res)
27
Quelques recommandations: I/O
Code en langage python
• Saisie des entrées
▫ Cas d’une valeur entière
x=int(input())
▫ Cas de deux variables
n,k=map(int,input().split())
▫ Cas d’un tableau de valeurs entières
ai=list(map(int,input().split()))
• Affichage des résultats
▫ print(res)
28
Quelques recommandations: I/O
Code en langage Java
• Saisie des entrées
▫ Éviter l’utilisation de la classe Scanner (non
recommandée dans les compétitions)
▫ Utiliser la classe BufferedReader
Pour une variable entière
BufferedReader sc = new BufferedReader(new
InputStreamReader([Link]));
int n=[Link]([Link]());
Pour un tableau : String [] arr =[Link]().split(" ");
• Affichage des résultats
▫ [Link](res)
29
Quelques recommandations
• Utiliser C++ à la place du langage C
▫ Inclut la bibliothèque standard du langage C
▫ Inclut la bibliothèque Standard Template Library (STL) offrant
plusieurs routines
• Afin de minimiser les includes et les erreurs de compilation,
ajouter le header qui inclut toutes les bibliothèques standards
#include <bits/stdc++.h>
• Le template de votre code source aura la structure suivante :
#include <bits/stdc++.h>
using namespace std;
int main() {
//Taper votre code
return 0;
}
30
Quelques recommandations
• Bien lire le problème
• Bien identifier les types des variables
• Utiliser des fonctions standards pour trier un tableau, chercher
un élément dans un tableau, etc
▫ Minimiser le code à développer
▫ Gagner du temps
▫ Par exemple : pour le tri
En C++: sort(tab, tab+n)
En Java:
[Link]() trier les éléments d’un tableau
[Link]() trier les éléments d’une collection (e.g., Vector).
En python: [Link]()
• Soumettre votre solution si et seulement si elle est bien testée
▫ N’oublier pas que vous serez sanctionnés pour chaque soumission
erronée !
31
Déroulement du cours
• Création d’un compte sur codeforces
• Accéder au lien du Contest de chaque séance à l’avance
• Chaque séance sera notée selon le nombre de problèmes
résolus
▫ Note par problème : 20/nb problèmes
▫ -0.25 pour chaque soumission erronée, à l’exception
des 2 premières séances
32
Démonstration
• Lien du problème:
[Link]
33
Contest - Séance 1
[Link]
34
Discussion et leçons tirées
35
longueur des entiers
Math HomeWork
C/C++ (entiers) Java (entiers)
• short • byte
• int • short
• long • int
• long long • long
• La taille du type de données “long” n’est pas fixe
▫ Architecture
▫ Système d’exploitation
▫ Compilateur
Source : [Link]
36
Entiers en C/C++ et Java (2/3)
Dans quelques systèmes, le type « long » se comporte
comme le type « int » ou comme le type « long long »
Système d’exploitation Architecture taille
Windows IA-32 4 octets
Windows Intel® 64 or IA-64 4 octets
Linux IA-32 4 octets
Linux Intel® 64 or IA-64 8 octets
Mac OS X IA-32 4 octets
Mac OS X Intel® 64 or IA-64 8 octets
Source : [Link]
37
38
Problème Onze
• La solution triviale:
▫ Générer la suite Fibonnaci dans un tableau
▫ Parcourir les valeurs entre 1 et n et vérifier si elles
existent dans la suite ou pas
▫ Construire la chaine en ajoutant ‘O’ si la valeur est
un nombre Fibonnaci et ‘o’ sinon
La complexité d’une telle solution est dans le
cas pire de l’ordre de O(N2)
39
Problème Onze
• Une deuxième solution pour vérifier si un nombre n est
un nombre Fibonnacci
A number is Fibonacci if and only if one or both of
(5*n2 + 4) or (5*n2 – 4) is a perfect square
• Il faut tout d’abord développer une fonction qui
retourne vrai si le nombre X est carré parfait
▫ Un nombre est dit carré parfait s’il est le carré d’un entier
▫ Exemple : 9 est carré parfait car 9=3*3
• Parcourir les nombres de 1 à n est vérifier si (5*n2 + 4) or
(5*n2 – 4) est carré parfait
La complexité d’une telle solution est dans le
cas pire de l’ordre de O(N)
40
Problème Onze
• La nouvelle solution C++:
#include<bits/stdc++.h>
using namespace std;
bool perfectSquare (int n)
{
Fonction vérifiant
int s = sqrt(n);
si un nombre
return (s*s == n); est carré parfait
}
int main ()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
if (perfectSquare(5*i*i+4)||perfectSquare(5*i*i-4))
cout<<"O";
else
cout<<"o";
}
return 0;
}
41
Problème Onze
Chaînes de caractères en C
• 3ème solution
▫ Créer, allouer et initialiser un tableau S de
caractères de taille n à ‘o’
▫ Calculer uniquement les nombres Fibonacci qui
sont inférieurs à n
▫ Mettre à jour S[fibonnaci] à ‘O’
• Il faut faire attention
▫ la taille du tableau de caractères
▫ Le dernier caractère à insérer dans le tableau
à Éviter d’avoir des caractères bizarres à la fin de
votre chaîne
42
TLE et complexité
• La plupart des sites assurant la programmation
compétitive autorise l’exécution de 10^8 instructions
par seconde
=> Analyser le problème et identifier la complexité du
programme à développer respectant les contraintes
43
Résoudre un TLE (Time Limit Exceeded)
Prenons l’exemple : chercher dans un tableau de taille N une paire
d’éléments où la somme est égale à X, durant 1 seconde (i.e.,
time limit per test: 1 second)
• Cas 1 : 1 <=N<=10^3
▫ La solution naive avec 2 boucles donnera une complexité de l’ordre
O(N2)
▫ Dans ce cas pire, 10^6 instructions seront exécutés et c’est acceptable
puisque c’est inférieure à 10^8
▫ Une solution avec une complexité meilleure O(N) ou O(NlogN) sera
aussi acceptée
• Cas 2 : 1 <=N<=10^5
▫ La solution avec une complexité O(N2) génère une TLE
▫ Une solution avec une complexité O(N) ou O(NlogN) sera acceptée
• Cas 3: 1 <=N<=10^8
▫ La seule solution acceptée dans ce cas est de l’ordre O(N)
44
Problème 313783C: Math Homework
• Solution triviale : Deux boucles imbriquées
▫ 1ère boucle pour parcourir les différents tests (de 1 à t)
▫ 2ème boucle pour parcourir les entiers compris entre 2
et sqrt(N) pour vérifier s’il existe un entier impair qui
divise N)
àComplexité O(sqrt(N)*t)
▫ 1<t<104 && 1<N<1014 à Nombre d‘opérations = 1011 >
108
à TLE
à Il faut trouver un moyen pour réduire le nombre
d’opérations
à On n’a pas le choix : on doit parcourir tous les tests
à Par contre, on peut optimiser la 2ème boucle, en jouant
sur le pas
45
Séance 2
46
Les chaines de caractères en C++
• La classe string (#include<string>)
▫ Déclaration et initialisation :
string s1;
string s2= "BONJOUR";
▫ Saisie d’une chaine sans espace: cin>>s;
▫ Saisie d’une chaine avec espace : getline(cin,s);
▫ Concaténation : string s3=s2+s1;
• Quelques fonctions utiles:
▫ [Link](): renvoie la taille de la chaine
▫ [Link](i): récupére le ième caractère ≅ Ch[i]
▫ [Link](pos,nb): renvoie nb caractères à partir de
pos
▫ [Link](pos): renvoie la sous chaine à partir de pos
Source :[Link]
47
Les chaines de caractères en C++
• Autres fonctions (#include<ctype.h>):
▫ tolower (char c) : convertir un caractère en minuscule
▫ toupper(char c) : convertir un caractère en majuscule
▫ islower(char c): vérifier si le caractère est minuscule
▫ isupper(char c): vérifier si le caractère est majuscule
▫ Etc.
Source : [Link]
48
Les chaines de caractères en C++
Exemple :
#include <bits/stdc++.h>
using namespace std;
int main()
{
string ch2="Hello_String";
cout << ch2 << endl;
cout << [Link]() << endl; //renvoie 12
cout << [Link](0,5) << endl; //renvoie Hello
cout<<[Link](5,1)<<endl; // renvoie _
cout << [Link](6) << endl; // renvoie String
cout<<[Link]()<<endl; // renvoie g
ch2.push_back('_'); // ajouter '_' à la fin
cout << ch2 << endl; // retourne Hello_String_
[Link]("C++"); // retourne Hello_String_C++
cout << ch2 << endl;
[Link](0,5,"Bonjour");// retourne Bonjour_String_C++
cout << ch2 << endl;
return 0;
}
49
Contest - Séance 2
[Link]
50
Séance 3
51
Structures de données en C++
• Vector : tableau dynamique
• Vector of pairs : tableau de paires
• Deque (double ended queue): tableau
dynamique auquel on peut ajouter des éléments
aux deux extrémités
• Stack : structure LIFO (Last In First Out)
appelée aussi Pile
• Queue : structure FIFO (First In First Out)
appelée aussi File.
• Set : ensemble ordonné
• Map : tableau associatif ordonné par clé
52
Opérations de base à étudier
• Les opérations de base définies sur ces
structures sont comme suit:
▫ Tester si la structure est vide
▫ Ajouter un élément à la structure
▫ Récupérer un élément à une position i de la
structure
▫ Vérifier si un élément appartient à la structure
▫ Supprimer un élément de la structure
53
Structures de données en C++: Vector (1/2)
#include <iostream> • #include <vector>
#include<vector> • Déclaration
▫ vector<int> tab : vecteur vide
using namespace std;
▫ vector <int>tab(5,4): vecteur de 5
int main() cases ayant la valeur 4
{ ▫ vector<int>tab2(tab): copie de tab
vector<int> tab; • Utilisation des [] pour accéder aux
tab.push_back(12); éléments du vecteur
tab.push_back(30);
tab.push_back(30); • Méthodes les plus utilisées
for(int i(0);i< [Link]() ;++i)
▫ push_back(nb) : ajouter nb à la fin
cout<<tab[i]<<endl;
tab.pop_back(); ▫ pop_back() : supprimer la dernière
[Link](1) =100; case
for(int i(0);i<[Link]();++i) ▫ size(): renvoyer la taille du vecteur
cout<<tab[i]<<endl; ▫ at(position) : joue le même rôle
return 0; que l’opérateur []
}
54
Structures de données en C++ : Vector (1/2)
#include <iostream> • Utilisation d’un iterator
#include<vector> pour parcourir le vecteur
using namespace std;
• [Link](): retourne un
int main() itérateur qui pointe sur le
{ premier élément
vector<int> tab; • [Link](): retourne un
vector<int>::iterator it; itérateur qui pointe sur le
tab.push_back(12); dernier élément
tab.push_back(30);
tab.push_back(20);
for(it=[Link]() ;it!=[Link]() ;++it)
cout<< *it<<endl;
return 0;
}
55
Structures de données en C++ : Vector of pairs
(1/2) • Pair : Un conteneur qui stocke
deux valeurs mappées l’une à
#include<bits/stdc++.h> l’autre
using namespace std; • Vector of pairs : un vecteur
int main() { qui contient plusieurs nombre
//declaring vector of pairs de telles paires (Pair)
vector< pair <int,int> > vect;
// initialising 1st and 2nd element of pairs with array values
int arr[] = {10, 20, 5, 40 };
int arr1[] = {30, 60, 20, 50};
int n = sizeof(arr)/sizeof(arr[0]);
// Entering values in vector of pairs
for (int i=0; i<n; i++)
vect.push_back( make_pair(arr[i],arr1[i]) );
// Printing the vector
for (int i=0; i<n; i++) {
// "first" and "second" are used to access 1st and 2nd element of pair,
respectively
cout << vect[i].first << ” " << vect[i].second << endl; }
return 0; }
56
Structures de données en C++: Vector of pairs
(2/2)
Trier le vecteur selon la 1ère valeur de la paire en utilisant la
fonction sort
sort([Link](), [Link]());
Trier le vecteur selon la 2ème valeur de la paire
sort([Link](), [Link](), sortbysec);
// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
return ([Link] < [Link]);
}
[Link]
57
Stack/ Pile
Trois opérations possibles
• Ajouter un élément ;
• Consulter le dernier élément ajouté ;
• Supprimer le dernier élément ajouté
58
Structures de données en C++ : stack
#include <iostream>
#include<stack>
using namespace std;
int main(){
stack<int> stk; //pile d'entiers
stack<string> s; //pile de chaînes de caractères
cout << "Le nombre d'éléments de la pile est : " << [Link]() << endl;
cout << "Etat de la pile : ";
if([Link]())
cout << "vide" << endl;
else
cout << "pas vide" << endl;
// empiler des élements
[Link](2);
[Link](3);
cout << "dernier elt" << [Link]() << endl;
//depiler
[Link]();
return 0;
}
59
Structures de données en C++ : queue
#include <iostream>
#include<queue>
using namespace std;
int main()
{
queue<int> file;
[Link](10);
[Link](20);
[Link](30);
cout << "front" << [Link]()<<endl;
cout << "back" << [Link]()<<endl;
cout << "size" << [Link]()<<endl;
[Link]();
cout << "front" << [Link]()<<endl;
return 0;
}
60
Structures de données en C++:deque
deque<int> d(4,5); • #include<deque>
deque<int>::iterator itd; • Par rapport au vecteur, un
d.push_front(2); deque offre des fonctions pour
d.push_back(8); manipuler les éléments se
for(int i(0); i<[Link](); ++i) trouvant en début de la
structure
cout << d[i] << " ";
▫ push_front
d.pop_back();
▫ pop_front
d.pop_front();
for(itd=[Link]();itd!=[Link]();++itd)
cout<< *itd<<" ";
61
Structures de données en C++ : set
#include <iostream>
#include<set> • Ensemble d’éléments
using namespace std;
int main(){ distincts
• ens.lower_bound(val) :
set<int> ens; retourne un itérateur qui
set<int>::iterator it, itL, itH;
[Link](13);
pointe sur la première
[Link](12); valeur dans l’ensemble qui
[Link](13); est supérieure ou égale
[Link](15); à val
cout <<[Link]()<<endl;
for(it=[Link]();it!=[Link]();++it) • ens.upper_bound(val):
cout << *it; retourne un itérateur qui
cout<<""<<endl; pointe sur la première
itL=ens.lower_bound(11); valeur dans l’ensemble qui
cout <<*itL<<endl;
itH=ens.upper_bound(13);
est strictement
cout <<*itH<<endl; supérieure à val
return 0;
}
62
Problème All letters avec Set
63
Structures de données en C++:map
#include <iostream>
#include<map>
using namespace std;
int main(){
string a;
map<string,int> dict;
dict["a"]=1; dict["b"]=22;dict["c"]=4;
for(int i=0;i<3;i++){
cin >>a;
dict[a]+=1;
}
map<string, int>::iterator it;
for(it=[Link]();it!=[Link]();++it){
cout<<"key"<<it->first<<" " <<"Value"<< it->second<<endl;
}
return 0;
}
64
Astuces de parcours des structures de
données : Set, Vector, Deque et map
vector<int> v; set<int> s;
v = {1, 2, 5, 2}; s = {4, 6, 2, 7, 4};
for (auto i: v) for (auto i: s)
cout << i << ’ ’; cout << i << ’ ’;
cout << '\n’; cout << '\n’;
// prints "1 2 5 2" // prints "2 4 6 7"
Ceci ne fonctionne pas pour Stack et Queue
65
Astuces de parcours des structures de
données : Set, Vector, Deque et map
deque<vector<pair<int, int>>> d;
d = {{{3, 4}, {5, 6}}, {{1, 2}, {3, 4}}};
for (auto i: d) {
for (auto j: i)
cout << [Link] << ' ' << [Link] << '\n’;
cout << "-\n"; }
// prints "3 4
// 5 6
// -
// 1 2
// 3 4
// -"
Ceci ne fonctionne pas pour Stack et Queue
66
Astuces de parcours des structures de
données : set, vector, deque et map
string a;
map<string,int> dict;
dict["a"]=1; dict[ "b" ]=22;dict["c"]=4;
for(int i=0;i<3;i++){
cin >>a;
dict[a]+=1;
}
for(auto i:dict)
cout<<"key"<<[Link]<<" " <<"Value"<< [Link]<<endl;
Ceci ne fonctionne pas pour Stack et Queue
67
Contest - Séance 3
[Link]
Avant de commencer !
Quelques indications utiles :
• Problem A (Free Fire ++) : Vector of pair + sorting
• Problem B (Different substrings) : set
• Problem C (Two letters): map
• Problem D (Shorter Text) : map
• Problem E (Regular Integer Sequence) : set
• Problem F (A well structured paranthesis sequence) : stack
• Problem G (Tunisian Revolution) : vector of pair + sorting
• Problem H (Problem Solving Lecture) : stack
