==Include(page="template/taskheader" task_id="cutii")==

==Include(page="template/taskheader" task_id="cutii")==
 
==include(page="template/badtests")==
 
Se dau $N$ cutii paralelipipedice prin dimensiunile lor ({$X, Y$} si {$Z$}). Se stie ca o cutie se poate pune in alta doar daca toate dimensiunile ei sunt strict mai mici cele ale cutiei in care va fi bagata. Se cere numarul maxim de cutii ce pot fi selectate din cele $N$ astfel incat ele sa poata fi "cuibarite" (o cutie va contine o cutie care la randul ei va contie o alta s.a.m.d. pana la cea mai mica care nu va mai contine nimic).
 
h2. Date de Intrare
 
Prima linie a fisierului $cutii.in$ va contine $N$ si $T$, reprezentand numarul de cutii si respectiv numarul de teste care vor urma. Pentru fiecare din cele $T$ teste vor urma cate $N$ linii continand $3$ numere reprezentand dimensiunile fiecarei cutii.
 
h2. Date de Iesire
 
Fisierul $cutii.out$ va contine $T$ linii pe fiecare linie un numar reprezentand numarul maxim de cutii ce pot fi alese pentru fiecare test.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 3500$
* $1 ≤ T ≤ 100$
* Dimensiunile cutiilor sunt date astfel fiecare dimensiune in parte (din cele trei posibile) ia toate valorile de la $1$ la $N$ in fiecare test din cele $T$ (valorile unei dimensiuni a cutiilor dintr-un test vor forma o permutare a numerelor de la $1$ la $N$).
* Timpul de executie a fost ales astfel incat $20%$ din el va fi folosit pentru citire si restul de $80%$ pentru calcularea rezultatelor
* $40%$ din teste vor avea $N ≤ 100$ iar restul vor avea $N = 3500$ si $T = 100$
* O cutie nu poate fi intoarsa in nici un fel (dimensiunile ei isi vor pastra ordinea)
 
h2. Exemplu
 
table(example). |_. cutii.in |_. cutii.out |
| 3 2
1 1 1
2 2 2
3 3 3
1 2 2
2 1 1
3 3 3
| 3
2 |
 
h3. Explicatii
 
Pentru primul set de cutii se selecteaza toate cutiile deoarece cutia cu numarul 2 se poate pune in cutia 3 iar cutia 1 in cea de-a doua. Pentru cel de-al doilea set se selecteaza cutiile 1 si 3 sau cutiile 2 si 3 neexistand posibilitatea de a le lua pe toate.
 
==Include(page="template/taskfooter" task_id="cutii")==
 
 

==Include(page="template/raw")==
 
Link: [1]File-List
 
Cutii
 
 
 
Se dau N cutii paralelipipedice prin dimensiunile lor (X, Y si Z). Se stie ca o cutie se poate pune in alta doar daca toate dimensiunile ei sunt strict mai mici cele ale cutiei in care va fi bagata. Se cere numarul maxim de cutii ce pot fi selectate din cele N astfel incat ele sa poata fi "cuibarite" (o cutie va contine o cutie care la randul ei va contie o alta s.a.m.d. pana la cea mai mica care nu va mai contine nimic).
 
h2. Date de Intrare
 
Prima linie a fisierului cutii.in va contine N si T, reprezentand numarul de cutii si respectiv numarul de teste care vor urma. Pentru fiecare din cele T teste vor urma cate N linii continand 3 numere reprezentand dimensiunile fiecarei cutii.
 
h2. Date de Iesire
 
Fisierul cutii.out va contine T linii pe fiecare linie un numar reprezentand numarul maxim de cutii ce pot fi alese pentru fiecare test.
 
h2. Restrictii si precizari
 
S 1 <= N <= 3.500
 
S 1 <= T <= 100
 
S Dimensiunile cutiilor sunt date astfel fiecare dimensiune in parte (din cele trei posibile) ia toate valorile de la 1 la N in fiecare test din cele T (valorile unei dimensiuni a cutiilor dintr-un test vor forma o permutare a numerelor de la 1 la N).
 
S Timpul de executie a fost ales astfel incat 20% din el va fi folosit pentru citire si restul de 80% pentru calcularea rezultatelor
 
S 40% din teste vor avea N <= 100 iar restul vor avea N = 3500 si T = 100
 
S O cutie nu poate fi intoarsa in nici un fel (dimensiunile ei isi vor pastra ordinea)
 
h2. Exemplu
 
cutii.in cutii.out Explicatii
3 2 3 Pentru primul set de cutii se selecteaza toate cutiile deoarece cutia cu numarul 2 se poate pune in cutia 3 iar cutia 1 in cea de-a doua. Pentru cel de-al doilea set se selecteaza cutiile 1 si 3 sau cutiile 2 si 3 neexistand posibilitatea de a le lua pe toate.
 
1 1 1 2
 
2 2 2
 
3 3 3
 
1 2 2
 
2 1 1
 
3 3 3
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/cutii/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="cutii")==

97