Fişierul intrare/ieşire:	fibosnek.in, fibosnek.out	Sursă	OJI 2023, clasa a 9-a
Autor	Eugen Nodea	Adăugată de	Moldovan Laura •laura2020
Timp execuţie pe test	0.15 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fibosnek

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).

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,
  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ă
• 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.

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;
• 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.

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

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.

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.

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.

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.

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

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