== include(page="template/taskheader" task_id="triticale") ==
Poveste si cerinta...
In dorinta sa de a-l invinge pe fermierul Jim la concursul de vite, fermierul John s-a gandit sa gaseasca un surplus de grane triticale pentru vacile sale Holstein. Triticale este o grana (tribulus multiplicatus) care creste foarte repede. Spre surpriza sa, John descopera ca baloturile de triticale nu sunt create uniform de masina de balotat. Fiecare balot este un paralelipiped de dimensiuni [$s1,s2,s3$]. Din fiecare dimensiune, John are un numar mare de baloturi. Problema pe care si-o pune acum este cum sa le aseze in hambar. Fiind dat un set de dimensiuni de baloturi si o cantitate suficienta de baloturi de fiecare dimensiune, trebuie sa se determine cum se pot ele stoca pana la o inaltime maxima. Evident, baloturile pot fi rotite in orice pozitie. Aranjarea lor in stiva trebuie sa tina cont de faptul ca un balot nu poate fi pus decat peste unul care are grosimea si latimea strict mai mari. Aceasta inseamna ca nu se poate pune un balot $[3,4,4]$ peste un balot $[4,4,4]$, deoarece oricum l-am orienta, nu vom obtine un balot cu grosime si latime strict mai mici de $4$.
h2. Date de intrare
...
Prima linie a fisierului de intrare, $triticale.in$ contine $N$, numarul de tipuri diferite de baloturi. Pe fiecare din urmatoarele $N$ linii se dau dimensiunile intregi ale baloturilor.
h2. Date de iesire
...
Pe prima linie a fisierului de iesire $triticale.out$ se tipareste inaltimea maxima a unei stive de baloturi care se poate construi cu regulile date. Pe liniile urmatoare se tiparesc dimensiunile fiecarui balot din stiva care poate constitui o solutie a problemei. Dimensiunile baloturilor se tiparesc de la varful stivei catre baza. Pe fiecare linie, primele doua numere sunt dimensiunile fetei paralele cu solul, primul numar mai mare sau egal cu al doilea. Al treilea numar este inaltimea balotului.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1000$
* Nici o dimensiune nu depaseste $16.000$
h2. Exemplu
table(example). |_. triticale.in |_. triticale.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
4 3 1
2 6 5
9 9 8
| 21
3 1 4
5 2 6
6 5 2
9 8 9
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="triticale") ==
