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.

Exemple. 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 :

- 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.

Exemple. 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 êtes à la tête d'une usine qui produit des châteaux de sable au Bourget-du-Lac. Vous voulez pouvoir vendre vos productions dans un certain nombre de villes (V la liste de ces villes). Vous avez des accords avec une entreprise de livraison. Celle-ci possède des liaisons depuis certaines villes vers d'autres villes. La question est de savoir le nombre minimal de nouvelles liaisons que vous devez créer pour pouvoir livrer toutes les villes de V.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec la liste V. Il suit une ligne avec un entier L indiquant le nombre de liaisons déjà proposées par les prestataires. Ensuite on trouve L nouvelles lignes : chacune correspond à une liaison déjà existante.
- Sortie : Le nombre minimal de nouvelles liaisons à rajouter à chaque test.
- Taille maximale des paramètres : valeurs des objets < 100, M < 40, N < 50.

Exemple. Sur l'entrée :

 Mexico, Katmandu, Grenoble, Tokyo
 2
 Katmandu -> Grenoble
 Mexico -> Katmandu

Il suffit de créer deux nouvelles liaisons, par exemple Bourget -> Tokyo et Bourget -> Mexico, pour pouvoir livrer toutes les villes de V. Donc la réponse attendue est 2.