Problem 508: cufere

Alex, eroina din Minecraft, este foarte curajoasă și 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$ rânduri, câte $9$ pe fiecare rând. Î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 atât compartimentele, cât și obiectele, cu numere construite după următoarea regulă:

un obiect are drept etichetă un număr natural cuprins între $10$ și $99$ , inclusiv, astfel: un număr prim, dacă este fragil, sau un număr compus, dacă este dur;
toate obiectele identice primesc aceeași etichetă;
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 având eticheta $94$ );
compartimentele goale sunt etichetate cu $0$ .

Alex vrea să rearanjeze obiectele din cufere, astfel încât:

să fie valorificat spațiul, adică să fie ocupate cât mai puține cufere și, în cadrul unui cufăr, cât mai puține compartimente;
să fie ocupate compartimentele din cuferele disponibile la rând, începând cu primul cufăr, și, în cadrul unui cufăr, începând cu primul rând și, în cadrul unui rând, de la stânga la dreapta. Cu alte cuvinte, se umple mai întâi cufărul $1$ , începând cu rândul $1$ , și pe fiecare rând de la stânga la dreapta, apoi cufărul al doilea, în aceeași manieră, și așa mai departe;
obiectele sunt preluate în ordinea crescătoare a etichetelor și din totalul obiectelor identice se formează mai întâi grupuri cu număr maxim de obiecte, și doar ultimul grup poate fi, eventual, incomplet;
fiecare din aceste grupuri se depozitează, pe măsura formării, în câte un compartiment al cufărului curențiar dacă acesta se umple, se trece la cufărul următor.

După rearanjarea obiectelor, compartimentele sunt etichetate din nou, după aceeași regulă.

Cerință

Dâ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 întâ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.

Date de intrare

Fișierul de intrare cufere.in conține pe prima linie numărul $c$ reprezentâ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, câte $9$ numere, reprezentând etichetele inițiale ale compartimentelor aflate pe câte un rând al unui cufăr, în ordinea în care ele se află în cufere, de la primul cufăr, până la ultimul, în cadrul fiecărui cufăr de la primul rând până la al treilea, iar în cadrul fiecărui rând de la stânga la dreapta. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

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șa o pereche formată din eticheta respectivă și numărul obiectelor cu această etichetă. Fiecare pereche de numere va fi afișată pe câte o linie.

Pentru cerința $2$ , etichetele compartimentelor vor fi afișate corespunzător plasării lor în cufere, câte $9$ pe fiecare linie a fișierului, de la primul cufăr până la ultimul, în cadrul fiecărui cufăr de la primul rând până la al treilea, iar în cadrul fiecărui rând de la stânga la dreapta.

Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Restricții și precizări

$c \in \{1,2\}$ ;
$1 \leq n \leq 10 \ 000$ ;
Eticheta unui obiect este cuprinsă intre $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.
Pentru $40$ de puncte, $c = 1$ ;
Pentru $60$ de puncte, $c = 2$ .

Exemplul 1

cufere.in

1
2
1488 1573 1437 4465 1099 1073 0 499 765
537 1173 4288 1273 2299 1555 1241 655 841
1141 237 5621 199 921 621 3465 1315 4155
1099 341 4765 6155 355 1099 6088 3988 255
4955 155 1329 1932 3099 114 3020 855 5555
1173 1388 673 2533 1488 1473 4033 2099 2065

cufere.out

Explicație

În acest exemplu se va rezolva cerința $c = 1$ și există $n = 2$ cufere. În cufere există:

$1$ obiect cu eticheta $14$ ;
$13$ obiecte cu eticheta $15$ ;
$30$ de obiecte cu eticheta $20$ ;
...
$107$ obiecte cu eticheta $99$ .

Exemplul 2

cufere.in

2
2
1488 1573 1437 4465 1099 1073 0 499 765
537 1173 4288 1273 2299 1555 1241 655 841
1141 237 5621 199 921 621 3465 1315 4155
1099 341 4765 6155 355 1099 6088 3988 255
4955 155 1329 1932 3099 114 3020 855 5555
1173 1388 673 2533 1488 1473 4033 2099 2065

cufere.out

114 1315 3020 6421 721 1329 1932 6433 133
1637 537 1641 1641 241 6455 6455 6455 4955
6465 6465 2465 1673 1673 1673 1673 1573 6488
6488 5488 6499 4399 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

Explicație

Î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ă câ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 încât primul cufăr este ocupat complet, primul rând al celui de-al doilea cufăr este parțial ocupat la stânga, iar ultimele sale două rânduri sunt goale.

cufere

Cerință

Date de intrare

Date de ieșire

Restricții și precizări

Exemplul 1

Explicație

Exemplul 2

Explicație

Log in or sign up to be able to send submissions!