Fişierul intrare/ieşire: | cutii.in, cutii.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 1024 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile 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×2x3 poate fi folosită şi cu dimensiunile 2×1x3, 3×2x1 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. |