| pack |
|
Muzeul municipal se mută în altă locaţie şi toate cele n obiecte expuse trebuie transportate. Avem la dispoziţie m cutii în care le putem împacheta. Fiindcă obiectele sunt foarte valoroase trebuie să găsim o modalitate de împachetare cât mai sigură. Pentru simplitate vom considera obiectele şi cutiile de forma paralelipipedică. Dacă un obiect de dimensiuni (x,y,z) este împachetat într-o cutie de dimensiuni (a,b,c), definim gradul de siguranţă ca: max(a-x,b-y,c-z). Evident, obiectele se pot roti, pentru a obţine un grad de siguranţă mai mic. Un obiect nu se poate împacheta intr-o cutie care are o mărime corespunzătoare mai mică, adică, pentru a putea împacheta obiectul trebuie ca a>=x, b>=y şi c>=z. Cerinţă Să se găsească modalitatea de împachetare prin care se minimizează cel mai mare grad de siguranţă.Date de intrare Pe prima linie a fişierului de intrare pack.in se află numărul n al obiectelor. Pe următoarele n linii se găsesc câte trei numere întregi reprezentând mărimea obiectelor. Pe a (n+2)-a linie se află numărul m al cutiilor. Pe următoarele m linii se găsesc câte trei numere întregi reprezentând dimensiunile cutiilor. Date de ieşire Pe prima linie a fişierului de ieşire pack.out să se afişeze gradul de siguranţă minim cu care se poate realiza împachetarea. Pe următoarele n linii se vor scrie câte două numere i şi j cu semnificaţia că obiectul i s-a împachetat în cutia j. Dacă nu se pot împacheta toate obiectele, în fişierul de ieşire se va afişa -1.Restricţii
Exemplu
|