INFO704 : Analyse d'algorithmes

Responsable 2021: Sébastien Tavenas

Adresse couriel : sebastien.tavenas@univ-smb.fr

Problèmes

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.

Problème 2 :

- 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 < 40, N < 50.