Prolego™ – Qualification 2013

Niveau 4

Énoncé

Vous possédez un jeu de N briques de dimensions (xi, yi, zi), ainsi qu'une machine vous permettant de dupliquer des briques. Vous pouvez orienter les briques comme bon vous semble, et les empiler pour former une tour de briques. Cependant, pour que la construction soit stable, vous ne pouvez poser une brique i sur une brique j que si la base de la brique du dessus est strictement incluse dans la base de la brique du dessous : elles ont respectivement des dimensions a × b et a' × b' telles que (a < a' et b < b') ou (a < b' et b < a'). Quelle est la hauteur de la plus grande tour que vous pouvez construire ?

Entrée

L'entrée comprendra :

  • un nombre N, le nombre de briques que vous avez au départ ;
  • sur les N lignes suivantes, les dimensions de chaque brique (xi, yi, zi).

Sortie

Vous afficherez en sortie :

  • la hauteur de la plus grande tour que vous pouvez construire.

Contraintes

  • 1 <= N <= 2 000
  • 1 <= xi, yi, zi <= 10 000 000
  • La hauteur de la plus grande tour ne dépasse jamais 100 000 000

Contraintes d'exécution

Utilisation mémoire maximum
2000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
1 4 1
2 5 3
4 4 4
Exemple de sortie
13
Exemple d'entrée
4
1 4 8
1 8 5
2 7 2
3 6 6
Exemple de sortie
15
Commentaire

La réponse est 15, par exemple on peut empiler :

  • (8, 5, hauteur 1)
  • (6, 3, hauteur 6)
  • (5, 1, hauteur 8) (une autre brique de mêmes dimensions que la première).