INFO704 : Analyse d'algorithmes

Responsable 2021: Sébastien Tavenas
Adresse courriel : sebastien.tavenas@univ-smb.fr

Problèmes (thème de la programmation dynamique)

Problème 1 :

- Il y a N produits à acheter, chacun ayant un certain prix. Vous avez une somme E d'euros à votre disposition. Le but est d'obtenir le nombre maximum d'objets possible.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs N et E. La ligne suivante contient N entiers: la liste des prix des N produits.
- Sortie : Le nombre de produits que l'on peut obtenir à chaque test.
- Taille maximale des paramètres : N,E < 10^5.
- Fichiers de tests : small_input, test100, test100000, solution_small_input, solution100
- Exemples de solutions : Code python, Code c++

Exemple d'un test. Sur l'entrée :

 5 10
 2 7 4 3 6

On a assez d'argent pour acheter les produits 1, 3 et 4. On ne peut pas acheter 4 produits. Donc la réponse attendue est 3.

Problème 2 :

- Une échelle à H barreaux. Lorsqu'on se trouve sur un barreau, on peut soit monter au barreau juste au-dessus, soit sauter le prochain barreau pour aller deux crans au-dessus (nos jambes ne sont pas assez longues pour sauter deux barreaux d'un coup). On veut savoir combien il y a de façons d'aller sur le dernier barreau (sans jamais redescendre). 
Comme ce nombre grossit très vite, on demandera juste le résultat modulo 123456789.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 1 ligne qui contient un entier H correspondant au nombre de barreaux de l'échelle. 
- Sortie : Le nombre de montées possibles pour chaque test (modulo 123456789).
- Taille maximale des paramètres : H < 10^8.
- Fichiers de tests : inputs
- Exemples de solutions : Code python, Code c++

Exemple d'un test. Sur l'entrée :

 2

On peut soit monter les deux barreaux d'un coup (en sautant le premier barreaux), soit monter d'abord sur le premier barreau et ensuite sur le second. Donc la réponse attendue est 2.

Problème 3 :

- Devant vous, il y a N distributeurs. Chacun contient une pile de M objets. Quand vous mettez 1 euro dans un distributeur, le premier objet (le plus bas) de cette pile tombe et vous l'obtenez (donc si vous souhaitez un objet particulier, il va falloir prendre tous les objets au-dessous). Chaque objet a une certaine valeur. Le but est de maximiser la valeur obtenue avec une certaine somme d'euros E initiale.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs N, M et E. Ensuite on trouve N nouvelles lignes : chacune correspond à un distributeur. Sur ces lignes, on trouve les M valeurs des objets dans ce distributeur (la première valeur correspond au premier objet qui va tomber).
- Sortie : La valeur maximale que l'on peut obtenir à chaque test.
- Taille maximale des paramètres : valeurs des objets < 100, M < 100, N < 100.
- Fichiers de tests : small_input, dataDistrib10, dataDistrib50, dataDistrib100
- Exemples de solutions : Code python, Code c++

Exemple d'un test. Sur l'entrée :

 2 4 5
 2 1 10 3
 9 5 1 7

Avec 5 euros, on peut acheter les 3 premiers objets du premier distributeur (de valeurs 2, 1 et 10) et les deux premiers du deuxième distributeur de valeurs 9 et 5). Ce qui fait une valeur totale de 27. On ne peut pas obtenir plus. Donc la réponse attendue est 27.

Problème 4 :

- Vous vivez dans un quartier de New-York. La carte du quartier correspond à une grille (à coordonnées entières). Vous habitez en position (0,0) de cette grille (au sud-ouest) et vous travaillez en position (X,Y) (au nord-est). Pour changer, chaque matin, vous essayer d'aller au travail avec un nouveau chemin (mais vous avez seulement le temps de prendre un chemin rapide : à tout moment, vous devez vous déplacer soit vers l'est, soit vers le nord.). Vous aimeriez connaitre le nombre de  chemins possibles. Toutefois il y a un soucis, certaines routes sont bloquées. 
Ce nombre grossissant vite, on s'intéressera au résultat modulo 123456789.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs X,Y et B (le nombre de blocages dans le quartier). Ensuite on trouve B nouvelles lignes : chacune correspond à un blocage et est de la forme : 'a b d' où a et b sont des nombres et d (la direction du blocage) est soit 'h' (horizontal), soit 'v' (vertical). Par exemple, un blocage : '3 5 h' signifie que depuis la position (3,5), la route qui va vers l'est est bloquée.
- Sortie : Le nombre de chemins à chaque test.
- Taille maximale des paramètres : X < 10000, Y < 10000.
- Fichiers de tests : small_input, quartier10, quartier100, quartier1000, quartier10000

Exemple d'un test. Sur l'entrée :

 2 2 2
 1 0 'v'
 1 1 'v'

On peut vérifier que tous les chemins possibles sont HHVV, VHHV et VVHH (où H correspond à un pas horizontal et V à un pas vertical). Donc la réponse attendue est 3.

Problème 5 :

- Il y a D dés, chacun avec F faces. Nous voulons calculer la probabilité d'obtenir la somme S quand les dés sont lancés. en fait, il suffit de compter combien de fois la somme S peut être obtenue. Par exemple, avec 2 dés de 4 faces, il y a 3 façons d'obtenir la somme 6 : (2,4), (3,3) et (4,2). 
Ce nombre grossissant vite, on s'intéressera au résultat modulo 123456789.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test correspond à une ligne où apparaissent trois entiers D, F et S.
- Sortie : Le nombre de façons d'obtenir S à chaque test.
- Taille maximale des paramètres : D < 1000,  F < 1000, S < 500000.

Exemple d'un test. Sur l'entrée :

 2 4 6

Comme expliqué dans l'énoncé, la réponse attendue est 3.

Problème 6 :

- Un camion doit acheminer sa cargaison depuis la ville \(V_1\) vers la ville \(V_n\). Lors de ce voyage, il traverse les villes   \(V1\), \(V_2\), \(V_3\), ..., \(V_n\). À son départ, le camion a le réservoir plein : il contient \(m\) gallons d'essence. Pour aller d'une ville à la suivante le camion utilise un gallon d'essence. Toutefois, dans chacune des villes \(V_i\), le camion peut faire le plein en payant un prix \(C_i\) (si \(C_i =0\), cela signifie que la ville \(V_i\) ne possède pas de station d'essence et donc qu'il n'est pas possible de faire le plein ici). 

Donnés le nombre de villes n, la taille du réservoir m et le prix du plein dans chacune des villes tabPrix, trouver un algorithme qui identifie le coût minimal d'un tel voyage.

- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 2 lignes. La première contient deux entiers n et m correspondant au nombre de villes et à la capacité du réservoir. La seconde ligne contient n entiers correspondant aux prix du plein dans chaque ville.
- Sortie : Le prix minimal à payer lors de chaque test.
- Taille maximale des paramètres : n < 1000000, m < 10000, C < 100

Exemple d'un test. Sur l'entrée :

 5 2
 1 4 10 3 5  

Partant de la ville V1, on peut aller à la ville V2 et faire le plein (coût 4), puis aller à la ville V4, refaire le plein (coût 3) et on a assez pour arriver à la ville V5. Le coût optimal est donc de 7.

Problème 7 :

- Une suite de nombres est appelée en zig-zag si la différence entre les paires successives de nombres alterne entre positive et négative. Une suite avec au plus deux éléments est trivialement toujours en zig-zag. Par exemple, 1, 7, 4, 9, 2, 5 est une suite en zig-zag car les différences (6,-3,5,-7,3) alternent. Par opposition, les suites 1,4,7,2,5 et 1,7,4,5,5 ne sont pas en zig-zag. Donnée une suite d'entiers, le but est de trouver la longueur de la plus longue sous-suite qui est en zig-zag.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 2 lignes. La première contient un entier N correspondant à la taille de la suite. La seconde ligne contient N entiers correspondant aux valeurs de la suite.
- Sortie : La longueur de la plus grande sous-suite en zig-zag pour chaque test.
- Taille maximale des paramètres : valeurs des objets < 100, M < 40, N < 50.

Exemple d'un test. Sur l'entrée :

 10
 1, 17, 5, 10, 13, 15, 10, 5, 16, 8

Il y a plusieurs sous-suites en zig-zag de longueur 7, par exemple 1,17,10,13,10,16,8. Aucune n'a longueur 8. Donc la réponse attendue est 7.

Problèmes (thème des graphes)

Réseau téléphonique

Problème Labyrinthe :

Problème Livraison :