== include(page="template/taskheader" task_id="punga") ==
Poveste și cerință...
!>problema/punga?punga.gif!
Dănilă Prepeleac, negustor priceput, vrea să dea boii săi pe o pungă. Dar nu orice pungă! El are K cuburi identice, de latură unu, pe care vrea să le bage în pungă. Dănilă, om pretențios, cere să i se facă punga la comandă! Dar pungarul nu vrea să fabrice decît un anumit tip de pungi, care sînt mai mult cutii, căci au înălțime și lățime numere întregi, iar adîncimea este fixată întotdeauna la unu.
Dănilă, la rîndul său, plin de idei, are și el următoarele pretenții asupra pungii:
* În pungă trebuie să încapă cele K cuburi (desigur)
* Suma dintre înălțime și lățime să fie minimă
* Înălțimea să fie mai mare sau egală cu lățimea
* În caz că există mai multe pungi care satisfac primele trei cerințe Dănilă o vrea pe aceea cu volumul minim
h2. Cerință
Dat K, numărul de cuburi ale lui Dănilă Prepeleac, să se afișeze lățimea și înălțimea pungii.
h2. Date de intrare
Fișierul de intrare $punga.in$ ...
Fișierul de intrare $punga.in$ va conține pe prima linie un număr T ce reprezintă numărul de teste. Pe a doua linie se află, despărțite prin spații, T numere K[~i~], fiecare reprezentînd un număr de cuburi ale lui Dănilă pentru care trebuie să calculăm dimensiunile pungii.
h2. Date de ieșire
În fișierul de ieșire $punga.out$ ...
În fișierul de ieșire $punga.out$ se vor scrie T linii, corespunzătoare răspunsurilor la cele T teste. Pe fiecare linie i se vor afla două valori despărțite prin spațiu și anume lățimea și înălțimea (în această ordine!) a pungii cu numărul i. Punga i este dimensionată pentru numărul K[~i~] de la intrare.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ T ≤ 1000
* 1 ≤ K[~i~] < 2[^62^]
h2. Exemplu
h2. Exemple
table(example).
|_. punga.in |_. punga.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. punga.in |_. punga.out |_. Explicații |
| 3
17 92 257
| 3 6
8 12
13 20
| Sînt trei teste.
La primul test dimensionăm o pungă pentru 17 cuburi. Ele încap într-o pungă cu suma minimă
între înălțime și lățime de 9. Cea mai mică pungă este de 3 · 6 = 18 de cuburi.
Vezi desenul pentru exemplificare grafică. (Punga de 4 · 5 are un volum mai mare,
si anume de 20 de cuburi.)
În al doilea test dimensionăm o pungă pentru 92 de cuburi. Ele încap într-o pungă cu suma minimă
între înălțime și lățime de 20. Cea mai mică pungă este de 8 · 12 = 96 de cuburi.
În al treilea test dimensionăm o pungă pentru 257 de cuburi. Ele încap într-o pungă cu suma minimă
între înălțime și lățime de 33. Cea mai mică pungă este de 13 · 20 = 260 de cuburi.
|
== include(page="template/taskfooter" task_id="punga") ==
