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

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.
- 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', soit 'v'. 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 : valeurs des objets < 100, M < 40, N < 50.

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 :

- 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 d'un test. 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.