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

Vezi solutiile trimise | Statistici

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 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 ş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 având eticheta 94);
• compartimentele goale sunt etichetate cu 0.

Alex vrea s˘a rearanjeze obiectele din cufere, astfel ˆıncˆat:
• s˘a fie valorificat spat, iul, adic˘a s˘a fie ocupate cˆat mai put, ine cufere s, i, ˆın cadrul unui cuf˘ar, cˆat mai put, ine compartimente;
• s˘a fie ocupate compartimentele din cuferele disponibile la rˆand, ˆıncepˆand cu primul cuf˘ar, s, i, ˆın cadrul unui cuf˘ar,
ˆıncepˆand cu primul rˆand s, i, ˆın cadrul unui rˆand, de la stˆanga la dreapta. Cu alte cuvinte, se umple mai ˆıntˆai cuf˘arul
1, ˆıncepˆand cu rˆandul 1, s, i pe fiecare rˆand de la stˆanga la dreapta, apoi cuf˘arul al doilea, ˆın aceeas, i manier˘a, s, i as,a
mai departe;
• obiectele sunt preluate ˆın ordinea cresc˘atoare a etichetelor s, i din totalul obiectelor identice se formeaz˘a mai ˆıntˆai
grupuri cu num˘ar maxim de obiecte, s, i doar ultimul grup poate fi, eventual, incomplet;
• fiecare din aceste grupuri se depoziteaz˘a, pe m˘asura form˘arii, ˆın cˆate un compartiment al cuf˘arului curent, iar dac˘a
acesta se umple, se trece la cuf˘arul urm˘ator.
Dup˘a rearanjarea obiectelor, compartimentele sunt etichetate din nou, dup˘a aceeas, i regul˘a.

Cerinţe

Dˆandu-se cele n cufere, care cont, in obiectele ˆın ordinea init, ial˘a, Alex v˘a roag˘a s˘a realizat, i un program care s˘a determine:
1. pentru fiecare etichet˘a distinct˘a de obiect ˆıntˆalnit ˆın cele n cufere, num˘arul total al obiectelor cu acea etichet˘a;
2. noile etichete ale compartimentelor care compun cele n cufere, dup˘a rearanjarea obiectelor.

Date de intrare

Fis, ierul de intrare cufere.in cont, ine pe prima linie num˘arul c reprezentˆand cerint,a care trebuie s˘a fie rezolvat˘a (1 sau 2),
pe a doua linie num˘arul natural nenul n, cu semnificat, ia din enunt, , iar pe fiecare din urm˘atoarele 3n linii, cˆate 9 numere,
reprezentˆand etichetele init, iale ale compartimentelor aflate pe cˆate un rˆand al unui cuf˘ar, ˆın ordinea ˆın care ele se afl˘a ˆın
cufere, de la primul cuf˘ar, pˆan˘a la ultimul, ˆın cadrul fiec˘arui cuf˘ar de la primul rˆand pˆan˘a la al treilea, iar ˆın cadrul fiec˘arui
rˆand de la stˆanga la dreapta. Numerele aflate pe aceeas, i linie a fis, ierului sunt separate prin cˆate un spat, iu.

Date de ieşire

Fis, ierul cufere.out va cont, ine fie r˘aspunsul pentru cerint,a 1 (dac˘a c = 1), fie r˘aspunsul pentru cerint,a 2 (dac˘a c = 2).
Pentru cerint,a 1, pentru fiecare etichet˘a distinct˘a, ˆın ordine strict cresc˘atoare, se va afis,a o pereche format˘a din eticheta
respectiv˘a s, i num˘arul obiectelor cu aceast˘a etichet˘a. Fiecare pereche de numere va fi afis,at˘a pe cˆate o linie.
Pentru cerint,a 2, etichetele compartimentelor vor fi afis,ate corespunz˘ator plas˘arii lor ˆın cufere, cˆate 9 pe fiecare linie a
fis, ierului, de la primul cuf˘ar pˆan˘a la ultimul, ˆın cadrul fiec˘arui cuf˘ar de la primul rˆand pˆan˘a la al treilea, iar ˆın cadrul
fiec˘arui rˆand de la stˆanga la dreapta.
Numerele aflate pe aceeas, i linie a fis, ierului sunt separate prin cˆate un spat, iu.

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?