cufere

Cufere

== include(page="template/taskheader" task_id="cufere") ==

Alex, eroina din Minecrafţeste foarte curajoasă si harnică. De-a lungul timpului, ea a depozitat ı̂n n cufere tot felul de obiecte fragile (de exemplu ouă) sau dure (de exemplu pietre).

Alex, eroina din _Minecraft_, este foarte curajoasă si harnică. De-a lungul timpului, ea a depozitat ı̂n $n$ cufere tot felul de obiecte fragile (de exemplu ouă) sau dure (de exemplu pietre).

Un cufăr este o cutie de lemn cu 27 de compartimente dispuse pe 3 rânduri, câte 9 pe fiecare rând. Într-un compartiment poate fi depozitat un grup de unul sau mai multe obiecte identice: maximum 16 obiecte fragile sau maximum 64 de obiecte dure. Pot fi mai multe compartimente care să conţină acelaşi tip de obiecte, iar unele compartimente pot fi goale.

!{float: right; width: 350px; margin: 2px; }problema/cufere?cufere.png!
 
Un cufăr este o cutie de lemn cu $27$ de compartimente dispuse pe $3$ rânduri, câte $9$ pe fiecare rând. Într-un compartiment poate fi depozitat un grup de unul sau mai multe obiecte **identice**: maximum $16$ obiecte fragile sau maximum $64$ de obiecte dure. Pot fi mai multe compartimente care să conţină acelaşi tip de obiecte, iar unele compartimente pot fi goale.

Alex a etichetat atât compartimentele, cât si obiectele, cu numere construite după următoarea regulă:

* un obiect are drept etichetă un număr natural cuprins ı̂ntre 10 si 99,

* un obiect are drept etichetă un număr natural cuprins ı̂ntre $10$ si $99$,

inclusiv, astfel: un număr prim, dacă este fragil, sau un număr compus, dacă este dur;

Figura 1: Exemplu de cufăr ı̂nainte si după !problema/cufere?cufere.png!

* toate obiectele identice primesc aceeaşi etichetă; ordonare

* un compartiment are drept etichetă un număr natural format din două valori alipite: numărul obiectelor din grupul depozitat ı̂n el, urmat de eticheta comună a acestora (de exemplu dacă eticheta compartimentului este 1994, ı̂nseamnă că ı̂n el este depozitat un grup de 19 obiecte, fiecare având eticheta 94);
* compartimentele goale sunt etichetate cu 0.

* un compartiment are drept etichetă un număr natural format din două valori alipite: numărul obiectelor din grupul depozitat ı̂n el, urmat de eticheta comună a acestora (de exemplu dacă eticheta compartimentului este $1994$, ı̂nseamnă că ı̂n el este depozitat un grup de $19$ obiecte, fiecare având eticheta $94$);
* compartimentele goale sunt etichetate cu $0$.

Alex vrea să rearanjeze obiectele din cufere, astfel ı̂ncât:

Alex vrea să **rearanjeze** obiectele din cufere, astfel ı̂ncât:

* să fie valorificat spaţiul, adică să fie ocupate cât mai puţine cufere şi, ı̂n cadrul unui cufăr, cât mai puţine compartimente;

* să fie ocupate compartimentele din cuferele disponibile la rând, ı̂ncepând cu primul cufăr, şi, ı̂n cadrul unui cufăr, ı̂ncepând cu primul rând şi, ı̂n cadrul unui rând, de la stânga la dreapta. Cu alte cuvinte, se umple mai ı̂ntâi cufărul 1, ı̂ncepând cu rândul 1, si pe fiecare rând de la stânga la dreapta, apoi cufărul al doilea, ı̂n aceeaşi manieră, si aşia mai departe;

* să fie ocupate compartimentele din cuferele disponibile la rând, ı̂ncepând cu primul cufăr, şi, ı̂n cadrul unui cufăr, ı̂ncepând cu primul rând şi, ı̂n cadrul unui rând, de la stânga la dreapta. Cu alte cuvinte, se umple mai ı̂ntâi cufărul $1$, ı̂ncepând cu rândul $1$, si pe fiecare rând de la stânga la dreapta, apoi cufărul al doilea, ı̂n aceeaşi manieră, si aşia mai departe;

* obiectele sunt preluate ı̂n ordinea crescătoare a etichetelor si din totalul obiectelor identice se formează mai ı̂ntâi grupuri cu număr maxim de obiecte, si doar ultimul grup poate fi, eventual, incomplet;
* fiecare din aceste grupuri se depozitează, pe măsura formării, ı̂n câte un compartiment al cufărului curenţiar dacă acesta se umple, se trece la cufărul următor.

h2. Cerinţe

Dându-se cele n cufere, care conţin obiectele ı̂n ordinea iniţială, Alex vă roagă să realizaţi un program care să determine:
1. pentru fiecare etichetă distinctă de obiect ı̂ntâlnit ı̂n cele n cufere, numărul total al obiectelor cu acea etichetă;
2. noile etichete ale compartimentelor care compun cele n cufere, după rearanjarea obiectelor.

Dându-se cele $n$ cufere, care conţin obiectele ı̂n ordinea iniţială, Alex vă roagă să realizaţi un program care să determine:
 
# pentru fiecare etichetă distinctă de obiect ı̂ntâlnit ı̂n cele n cufere, numărul total al obiectelor cu acea etichetă;
# noile etichete ale compartimentelor care compun cele n cufere, după rearanjarea obiectelor.

h2. Date de intrare

Fişierul de intrare cufere.in conţine pe prima linie numărul c reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2), pe a doua linie numărul natural nenul n, cu semnificaţia din enunţ, iar pe fiecare din următoarele 3n linii, câte 9 numere, reprezentând etichetele iniţiale ale compartimentelor aflate pe câte un rând al unui cufăr, ı̂n ordinea ı̂n care ele se află ı̂n cufere, de la primul cufăr, până la ultimul, ı̂n cadrul fiecărui cufăr de la primul rând până la al treilea, iar ı̂n cadrul fiecărui rând de la stânga la dreapta. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.

Fişierul de intrare $cufere.in$ conţine pe prima linie numărul $c$ reprezentând cerinţa care trebuie să fie rezolvată ({$1$} sau $2$), pe a doua linie numărul natural nenul $n$, cu semnificaţia din enunţ, iar pe fiecare din următoarele $3n$ linii, câte $9$ numere, reprezentând etichetele iniţiale ale compartimentelor aflate pe câte un rând al unui cufăr, ı̂n ordinea ı̂n care ele se află ı̂n cufere, de la primul cufăr, până la ultimul, ı̂n cadrul fiecărui cufăr de la primul rând până la al treilea, iar ı̂n cadrul fiecărui rând de la stânga la dreapta. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.

h2. Date de ieşire

Fişierul cufere.out va conţine fie răspunsul pentru cerinţa 1 (dacă c = 1), fie răspunsul pentru cerinţa 2 (dacă c = 2).
Pentru cerinţa 1, pentru fiecare etichetă distinctă, ı̂n ordine strict crescătoare, se va afişia o pereche formată din eticheta respectivă şi numărul obiectelor cu această etichetă. Fiecare pereche de numere va fi afişiată pe câte o linie.

Fişierul $cufere.out$ va conţine fie răspunsul pentru cerinţa $1$ (dacă $c = 1$), fie răspunsul pentru cerinţa $2$ (dacă $c = 2$).
Pentru cerinţa $1$, pentru fiecare etichetă distinctă, ı̂n ordine strict crescătoare, se va afişa o pereche formată din eticheta respectivă şi numărul obiectelor cu această etichetă. Fiecare pereche de numere va fi afişată pe câte o linie.

Pentru cerinţa 2, etichetele compartimentelor vor fi afişiate corespunzător plasării lor ı̂n cufere, câte 9 pe fiecare linie a fişierului, de la primul cufăr până la ultimul, ı̂n cadrul fiecărui cufăr de la primul rând până la al treilea, iar ı̂n cadrul fiecărui rând de la stânga la dreapta.

Pentru cerinţa $2$, etichetele compartimentelor vor fi afişate corespunzător plasării lor ı̂n cufere, câte 9 pe fiecare linie a fişierului, de la primul cufăr până la ultimul, ı̂n cadrul fiecărui cufăr de la primul rând până la al treilea, iar ı̂n cadrul fiecărui rând de la stânga la dreapta.

Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.
h2. Restricţii

* c ∈ {1, 2}
* 1 ≤ n ≤ 10 000
* Eticheta unui obiect este cuprinsă ı̂ntre 10 şi 99, inclusiv.
* În cazul cerinţei 2, se vor afişia etichetele pentru toate compartimentele, chiar dacă ele sunt goale sau provin din cufere complet goale

* $c ∈ {1, 2}$
* $1 ≤ n ≤ 10 000$
* $Eticheta unui obiect este cuprinsă ı̂ntre 10 şi 99, inclusiv$.
* $În cazul cerinţei 2, se vor afişa etichetele pentru toate compartimentele, chiar dacă ele sunt goale sau provin din cufere complet goale.$

h2. Exemple

| cufere.in | cufere.out |

table(example). |_. cufere.in |_. cufere.out |

|^. 1
2
1488 1573 1437 4465 1099 1073 0 499 765

h3. Exemplul 1

În acest exemplu se va rezolva cerinţa c = 1 şi există n = 2 cufere. În cufere există:
* 1 obiect cu eticheta 14;
* 13 obiecte cu eticheta 15;
* 30 de obiecte cu eticheta 20;
* ...
* 107 obiecte cu eticheta 99.

În acest exemplu se va rezolva cerinţa $c = 1$ şi există $n = 2$ cufere. În cufere există:
 
* $1 obiect cu eticheta 14;$
* $13 obiecte cu eticheta 15;$
* $30 de obiecte cu eticheta 20;$
* $...$
* $107 obiecte cu eticheta 99.$

h3. Exemplul 2

În acest exemplu se va rezolva cerinţa c = 2 şi există n = 2 cufere. După rearanjare, s-au plasat obiectele ı̂n ordinea crescătoare a etichetelor. Pentru primele trei etichete se formează câte un singur grup, aceastea fiind plasate ı̂n primele trei compartimente ale primului cufăr. Apoi, cele 71 de obiecte cu eticheta 21 (dure), sunt ı̂mpărţite ı̂ntr-un grup de 64 (ı̂n compartimentul al patrulea), şi un grup de 7 (ı̂n compartimentul al cincilea). La fel se procedează şi cu celelalte obiecte, astfel ı̂ncât primul cufăr este ocupat compleţprimul rând al celui de-al doilea cufăr este parţial ocupaţla stânga, iar ultimele sale două rânduri sunt goale.

În acest exemplu se va rezolva cerinţa $c = 2$ şi există $n = 2$ cufere. După rearanjare, s-au plasat obiectele ı̂n ordinea crescătoare a etichetelor. Pentru primele trei etichete se formează câte un singur grup, aceastea fiind plasate ı̂n primele trei compartimente ale primului cufăr. Apoi, cele $71$ de obiecte cu eticheta 21 (dure), sunt ı̂mpărţite ı̂ntr-un grup de $64$ (ı̂n compartimentul al patrulea), şi un grup de $7$ (ı̂n compartimentul al cincilea). La fel se procedează şi cu celelalte obiecte, astfel ı̂ncât primul cufăr este ocupat compleţprimul rând al celui de-al doilea cufăr este parţial ocupaţla stânga, iar ultimele sale două rânduri sunt goale.

== include(page="template/taskfooter" task_id="cufere") ==