Fișierul intrare/ieșire: cutii.in, cutii.out Sursă ad-hoc
Autor din folclor Adăugată de Catalin.FrancuCătălin Frâncu •Catalin.Francu
Timp execuție pe test 0.3 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile trimise | Statistici

Cutii (clasele 9-10)

Ion are N tipuri de cutii paralelipipedice de dimensiuni cunoscute. Există un număr infinit de cutii din fiecare tip. Ion vrea să construiască un turn cât mai înalt punând cutii una peste alta după următoarele reguli:

  • O cutie cu dimensiunile bazei a x b poate fi pusă peste alta cu dimensiunile bazei c x d numai dacă baza primei cutii se încadrează complet în baza celei de-a doua, așadar a < c și b < d.
  • Cutiile pot fi rotite. Cu alte cuvinte, o cutie cu dimensiunile 1×2×3 poate fi folosită și cu dimensiunile 2×1×3, 3×2×1 etc.

Aflați înălțimea maximă a unui turn de cutii.

Date de intrare

Fișierul de intrare cutii.in conține pe prima linie numărul de tipuri de cutii, N. Pe următoarele N linii se află câte trei numere întregi, despărțite prin spațiu, indicând dimensiunile unui tip de cutie.

Date de ieșire

În fișierul de ieșire cutii.out se va scrie un singur număr, reprezentând înălțimea maximă a unui turn ce poate fi construit conform regulilor.

Restricții

  • 1 ≤ N ≤ 2.000
  • Dimensiunile cutiilor sunt cuprinse între 1 și 1.000.000.000.

Exemplu

cutii.in cutii.out Explicație
3
5 7 4
6 2 8
1 3 5
 20
 Așezăm una peste alta cutiile:
1×3 de înălțime 5;
2×6 de înălțime 8;
4×7 de înălțime 5;
6×8 de înălțime 2.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii