TME 5 - Programmation dynamique

0. Échauffement

Comme nous savons que vous adorez additionner des entiers, on vous donne n entiers et vous devez en calculer leur somme.

Le fichier d'entrée contient 1 entier par ligne, la première ligne contient 1≤n≤1000000 et les lignes suivantes contiennent les entiers 0≤A[i]≤1000000. Ajoutez la réponse à cette URL.

Vérifiez bien que le type de variable que vous utilisez suffit pour stocker le résultat, combien de bits sont nécessaires pour stocker la valeur 1e12 ?

1. Sous-séquence contiguë de valeur maximale

On vous donne une séquence de n entiers A[0] à A[n-1] et il faut déterminer deux indices 0≤i≤j≤n tel que la somme A[i]+A[i+1]+...+A[j] soit maximale.

Le fichier d'entrée contient 1 entier par ligne, la première ligne contient 1≤n≤1000000 et les lignes suivantes contiennent les entiers A[0] à A[n-1]. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
8 3 -5 10 -2 8 -3 -6 7	16	16 = 10 -2 +8

2. Rendre la monnaie

On vous donne n valeurs de pièces v[0] < v[1] < ... < v[n-1] (tous des entiers positifs). Supposons que v[0] = 1, pour que ce problème admette toujours une solution. Donnez un algorithme qui rend la monnaie pour un montant donnée C utilisant le moins de pièces que possible. On dispose d'une source inépuisable de pièces. (Ça fait rêver, pas vrai ?)

Dans le fichier d'entrée la première ligne contient les entiers 1≤n≤100 et 1≤C≤10000, et les lignes suivantes contiennent les entiers v[0] à v[n-1]. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
4 16 1 3 4 10	3	16 = 10 + 3 + 3

3. Plus longue sous-séquence croissante

On vous donne une séquence de n entiers A[0] à A[n-1] et il faut trouver la longueur de la plus longue sous-séquence strictement croissante.

Le fichier d'entrée contient 1 entier par ligne, la première ligne contient 1≤n≤1000000 et les lignes suivantes contiennent les entiers A[0] à A[n-1]. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
16 9 3 1 4 1 5 9 2 6 5 4 5 3 9 7 9	6	1 2 4 5 7 9

4. Empilement de boîtes

On vous donne un ensemble de n types de boîtes rectangulaire, où la i-ème boîte a une hauteur h[i], une largeur w[i] et une profondeur d[i] (tous des nombres entiers positifs). Vous voulez créer une pile de boîtes aussi haute que possible. Mais vous pouvez placer une boîte au dessus une autre seulement si les dimensions de la base de la boîte en dessous sont strictement plus grandes que la base de la boîte en dessus. Il est possible de tourner les boîtes, afin que tous les côtés peuvent servir de base. Il est également possible d'utiliser plusieurs instances d'un même type de boîte.

Le fichier d'entrée contient n+1 lignes, la première ligne contient 1≤n≤1000 et les n lignes suivantes contiennent les entiers h[i], w[i] et d[i] séparés par des blancs. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
4 10 2 1 4 4 4 5 6 7 8 1 1	26	l'empilement de boîtes en format (w,p,h) sont dans l'ordre 2 1 10 4 4 4 5 6 7 6 7 5

5. Construction de ponts

Considérons une carte planaire avec une rivière horizontale passant à travers le centre. Il y a n villes sur la rive sud avec les coordonnées x a[0] ... a[n-1] (toutes distinctes) et n villes sur la rive nord avec les coordonnées x b[0] ... b[n-1] (également toutes distinctes). Vous voulez connecter autant de paires de villes nord-sud avec des ponts droits, tel que les ponts ne se croisent pas. Les connexions ne sont possible seulement entre la i-ème ville du nord avec la i-ème ville du sud.

Le fichier d'entrée contient n+1 lignes, la première ligne contient 1≤n≤100000 et les n lignes suivantes contiennent les entiers a[i] et b[i] séparés par des blancs. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
6 13 9 0 2 7 0 5 4 10 7 11 12	4

6. Sac à dos

Vous avez n objets. Le i-ème objet a un poids p[i] et une valeur v[i]. Vous avez un sac à dos de capacité C. Trouvez une sélection d'objets dont le poids total ne dépasse pas C et dont la valeur totale soit maximale.

Le fichier d'entrée contient n+1 lignes, la première ligne contient n et C, puis les n lignes suivantes contiennent les entiers p[i] et v[i] séparés par des blancs. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
6 100 25 80 40 70 70 85 15 40 20 75 5 65	290	La solution consiste à prendre les éléments 0, 1, 4 et 5 avec un poids total de 90 et une valeur totale de 290.

7. Compter le nombre de parenthésages booléens

On vous donne une expression booléenne consistant en une chaîne des symboles 'true', 'false', 'and', 'or', et 'xor'. On a vu en début de TME que vous adorez compter. Alors comptez le nombre de possibilités de placer des parenthèses dans cette expression, tel qu'elle s'évalue à 'true'. Comme la réponse pourrait être très grande on veut la réponse modulo 100000007.

Le fichier d'entrée contient 2 lignes, la première ligne contient n et la deuxième contient 1≤n≤201 symboles séparés par des blancs. Chaque symbole est une chaîne parmi 'true', 'false', 'and', 'or', et 'xor', alternant constantes et opérateurs. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
7 false and false xor true or false	2	((false and false) xor true) or false = true (false and (false xor true)) or false = false (false and false) xor (true or false) = true false and (false xor (true or false)) = false false and ((false xor true) or false) = false

8. Stratégie optimale pour un jeu

Le fichier d'entrée contient n+1 lignes, la première ligne contient n et les lignes suivantes contiennent les entiers v[i]. Ajoutez la réponse à cette URL.

Exemple d'entrée	Réponse attendue	Explication
4 8 5 4 2	12

Une correction