INFO704 : Analyse d'algorithmes
BONJOUR en ce 11 octobre 2021 !!!!
Si un étudiant lit ce message, est-ce que vous pouvez me contacter dès que vous pouvez par courriel (ci-dessous). J'essaye de trouver depuis 30 minutes une adresse où vous joindre !
Au passage, un lien zoom où me joindre : https://zoom.us/j/98113552900?pwd=ZWwvYkd2SkVRT2cvMkNpekdJQVJPZz09
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
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
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
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', 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 : X < 1000, Y < 1000. - Fichiers de tests : small_input, quartier10, quartier100, quartier1000
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 < 10000, F < 1000, S < 1000.
Exemple d'un test. Sur l'entrée :
2 4 6
Comme expliqué dans l'énoncé, la réponse attendue est 3.