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

Se consideră o matrice cu n linii şi m coloane ce conţine numere naturale nenule.
Se defineşte o parcurgere snek a matricei un şir de valori obţinut astfel: se parcurg elementele matricei coloană cu coloană, de la prima până la ultima, şi, ı̂n cadrul fiecărei
coloane, de sus ı̂n joş de la elementul aflat pe prima linie, până la cel aflat pe ultima linie, ca ı̂n exemplu.

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.

Şirul numerelor Fibonacci este definit mai joşunde fib[k] reprezintă al k-lea număr

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

Fibonacci:
• fib[1] = 1, fib[2] = 1
• fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2

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

Se numeşte secvenţă fibosnek un termen sau o succesiune de termeni aflaţi pe poziţii consecutive ı̂n parcurgerea snek, cu proprietatea că fiecare dintre ei este număr Fibonacci. Similar, se numeşte secvenţă non-fibosnek un termen sau o succesiune de termeni aflaţi pe poziţii consecutive ı̂n parcurgerea snek, cu proprietatea că niciunul dintre ei nu este număr Fibonacci. Lungimea secvenţei este egală cu numărul termenilor săi. Suma secvenţei este egală cu suma termenilor săi.

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

15311
28113
4298

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

Figura 1: Exemplu de parcurgere snek a unei matrice cu 3 linii şi 4 coloane.

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

!problema/fibosnek?Poza.jpg!

h2. Cerinţe

Ordinea parcurgerii celulelor este:
1, 2, 4, 5, 8, 2, 3, 1, 9, 11, 13, 8
Numerele Fibonacci au fost evidenţiate.

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.

O secvenţă non-fibosnek poate fi transformată ı̂n una fibosnek prin ı̂nlocuirea fiecărui număr din secvenţă cu un număr
Fibonacci aflat cel mai aproape de el ı̂n şirul numerelor Fibonacci. Dacă există două numere Fibonacci la fel de apropiate de numărul daţse va alege mereu cel mai mic. De exemplu, secvenţa (4) se transformă ı̂n secvenţa (3), iar secvenţa (9, 11) ı̂n secvenţa (8, 13).

h2. Date de intrare

h3. Cerinţe

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.

Fiind date elementele matricei cu n linii şi m coloane să se determine:

h2. Date de ieşire

1. numărul de numere Fibonacci din matricea dată iniţial;
2. suma celei mai lungi secvenţe fibosnek ce poate fi obţinută, ştiind că se poate transforma cel mult o secvenţă non-fibosnek ı̂n una fibosnek folosind procedeul explicat mai sus. Dacă se pot obţine mai multe astfel de secvenţe de
lungime maximă, se va alege prima ı̂ntâlnită ı̂n parcurgerea snek a matricei.

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.

h3. Date de intrare

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.

Fişierul de intrare fibosnek.in conţine pe prima linie numerele naturale c, n şi m, unde c reprezintă cerinţa care trebuie
rezolvată (1 sau 2), iar n şi m au semnificaţia din enunţ, pe următoarele n linii conţine elementele matricei, parcurse
ı̂n ordine, linie cu linie şi ı̂n cadrul fiecărei linii, de la stânga la dreapta. Valorile aflate pe aceeaşi linie a fişierului sunt
separate prin câte un spaţiu.

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

h3. Date de ieşire

h2. Restricţii

Fişierul de ieşire fibosnek.out conţine fie doar numărul determinat pentru cerinţa 1 (dacă c = 1), fie doar suma determinată pentru cerinţa 2 (dacă c = 2).

* 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

h4. Restricţii
• c ∈ {1, 2}
• 1 ≤ n, m ≤ 1 500
• Elementele matricei au valori ı̂n intervalul [1, 231 − 1].
 
Restricţii
 
121c = 1 şi n, m ≤ 1 000
220c = 2 şi n, m ≤ 100
344c = 2 şi n, m ≤ 1 000
415c = 2 şi fără alte restricţii suplimentare
 
Exemple
 
| fibosnek.in | fibosnek.out |
| 1 3 4
1 5 3 11
2 8 1 13
4 2 9 8
2 3 4
1 5 3 11
2 8 1 13
4 2 9 8
2 4 4
2 4 7 1
3 3 6 7
5 5 8 4
11 8 13 6 | 9
61
42 |
 
h3. Explicaţii
 
h4.Exemplul 1
 
c = 1, n = 3, m = 4, iar matricea corespunde celei din Fig. 1. Există 9 numere Fibonacci ı̂n matrice: 1, 5, 3, 2, 8, 1, 13, 2, 8.
 
h4. Exemplul 2
 
c = 2, n = 3, m = 4, iar matricea corespunde celei din Fig. 1. Dacă se transformă secvenţa non-fibosnek (9, 11) ı̂n secvenţa fibosnek (8, 13), atunci cea mai lungă secvenţă fibosnek este (5, 8, 2, 3, 1, 8, 13, 13, 8), de lungime 9 şi sumă 61.
 
h4. Exemplul 3
 
Se transformă secvenţa non-fibosnek (11, 4) ı̂n secvenţa fibosnek (13, 3) şi se obţine secvenţa fibosnek (2, 3, 5, 13, 3, 3, 5, 8) de lungime 8 şi sumă 42. Deşi mai există o secvenţă fibosnek de lungime 8 ce se poate obţine prin transformarea secvenţei non-fibosnek (7, 6), aceasta nu a fost aleasă deoarece nu este prima secvenţă ce poate fi obţinută.