Fișierul intrare/ieșire cutii.in, cutii.out Sursă Cercul de informatică Vianu clasele 9-10
Autor din folclor Adăugată de avatar Catalin.Francu Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test 0.3 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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