== include(page="template/taskheader" task_id="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ă !problema/fibosnek?Poza.jpg!
* 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.

!problema/fibosnek?Poza.jpg!
Se consider˘a o matrice cu n linii s, i m coloane ce cont, ine numere naturale nenule.
Se defines, te o parcurgere snek a matricei un s, ir de valori obt, inut astfel: se parcurg
elementele matricei coloan˘a cu coloan˘a, de la prima pˆan˘a la ultima, s, i, ˆın cadrul fiec˘arei
coloane, de sus ˆın jos, de la elementul aflat pe prima linie, pˆan˘a la cel aflat pe ultima
linie, ca ˆın exemplu.
S, irul numerelor Fibonacci este definit mai jos, unde fib[k] reprezint˘a al k-lea num˘ar
Fibonacci:
• fib[1] = 1, fib[2] = 1
• fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2
Se numes, te secvent,˘a fibosnek un termen sau o succesiune de termeni aflat, i pe
pozit, ii consecutive ˆın parcurgerea snek, cu proprietatea c˘a fiecare dintre ei este num˘ar
Fibonacci. Similar, se numes, te secvent,˘a non-fibosnek un termen sau o succesiune de
termeni aflat, i pe pozit, ii consecutive ˆın parcurgerea snek, cu proprietatea c˘a niciunul
dintre ei nu este num˘ar Fibonacci. Lungimea secvent,ei este egal˘a cu num˘arul termenilor
s˘ai. Suma secvent,ei este egal˘a cu suma termenilor s˘ai.
O secvent,˘a non-fibosnek poate fi transformat˘a ˆın una fibosnek prin ˆınlocuirea fiec˘arui num˘ar din secvent,˘a cu un num˘ar
Fibonacci aflat cel mai aproape de el ˆın s, irul numerelor Fibonacci. Dac˘a exist˘a dou˘a numere Fibonacci la fel de apropiate
de num˘arul dat, se va alege mereu cel mai mic. De exemplu, secvent,a (4) se transform˘a ˆın secvent,a (3), iar secvent,a (9, 11)
ˆın secvent,a (8, 13).

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

h2. Cerinţe

Fiind date elementele matricei cu n linii s, i m coloane s˘a se determine:
1. num˘arul de numere Fibonacci din matricea dat˘a init, ial;
2. suma celei mai lungi secvent,e fibosnek ce poate fi obt, inut˘a, s, tiind c˘a se poate transforma cel mult o secvent,˘a
non-fibosnek ˆın una fibosnek folosind procedeul explicat mai sus. Dac˘a se pot obt, ine mai multe astfel de secvent,e de
lungime maxim˘a, se va alege prima ˆıntˆalnit˘a ˆın parcurgerea snek a matricei.

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.

h2. Date de intrare

Fis, ierul de intrare fibosnek.in cont, ine pe prima linie numerele naturale c, n s, i m, unde c reprezint˘a cerint,a care trebuie
rezolvat˘a (1 sau 2), iar n s, i m au semnificat, ia din enunt, , pe urm˘atoarele n linii cont, ine elementele matricei, parcurse
ˆın ordine, linie cu linie s, i ˆın cadrul fiec˘arei linii, de la stˆanga la dreapta. Valorile aflate pe aceeas, i linie a fis, ierului sunt
separate prin cˆate un spat, 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

Fis, ierul de ies, ire fibosnek.out cont, ine fie doar num˘arul determinat pentru cerint,a 1 (dac˘a c = 1), fie doar suma determinat˘a
pentru cerint,a 2 (dac˘a c = 2).

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.

h2. Restricţii
 
* $... ≤ ... ≤ ...$
 
h2. Exemplu

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

table(example). |_. fibosnek.in |_. fibosnek.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

h2. Restricţii

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

* 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