.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » pack

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
pack


Timp maxim de execuţie/test:
0.5 secunde
Memorie totală disponibilă/stivă:
16MB/4 MB

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

  • 1 <= n <= m <= 500
  • 1 <= x, y, z, a, b, c <= 1000
  • Dacă există mai multe soluţii puteţi afişa oricare dintre acestea.

Exemplu

pack.in pack.out
2
1 1 1
3 3 3
3
1 1 1
2 2 2
4 3 3
1
1 1
2 3
asist. Pătcaş Csaba
Universitatea Babeş-Bolyai, Cluj-Napoca
patcas.csaba@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom
De acelaşi autor: zeratul, miniasm, 3d, datorii, virus, tango
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
Despre cuplaj: cuvinte, joc4, algebra, felinar, atac2, site, graphgame, terenuri3d
surse trimise | ajutor