== 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.
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.
!{float: right; width: 350px; margin: 2px; }problema/fibosnek?fibosnek.png!
Alex a etichetat atât compartimentele, cât si obiectele, cu numere construite după următoarea regulă:
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 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.
Şirul numerelor Fibonacci este definit mai joş unde fib[k] reprezintă al k-lea număr Fibonacci:
Alex vrea să rearanjeze obiectele din cufere, astfel ı̂ncât:
* $fib[1] = 1, fib[2] = 1$
* $fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2$
* 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.
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.
După rearanjarea obiectelor, compartimentele sunt etichetate din nou, după aceeaşi regulă.
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 dat 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. 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.
Fiind date elementele matricei cu $n$ linii şi $m$ coloane să se determine:
# $numărul de numere Fibonacci din matricea dată iniţial;$
# $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.$
h2. 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.
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.
h2. 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.
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$).
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
Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.
* $c ∈ {1, 2}$
* $1 ≤ n, m ≤ 1 500$
* $Elementele matricei au valori ı̂n intervalul [1, 2^31^ − 1].$
h2. Restricţii
table(subtasks). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $21$ | $c = 1 şi n, m ≤ 1 000$ |
| $2$ | $20$ | $c = 2 şi n, m ≤ 100$ |
| $3$ | $44$ | $c = 2 şi n, m ≤ 1 000$ |
| $4$ | $15$ | $c = 2 şi fără alte restricţii suplimentare$ |
h2. Exemple
table(example). |_. fibosnek.in |_. fibosnek.out |
| 1 3 4
1 5 3 11
2 8 1 13
4 2 9 8 |^. 9 |
| 2 3 4
1 5 3 11
2 8 1 13
4 2 9 8 |^. 61 |
| 2 4 4
2 4 7 1
3 3 6 7
5 5 8 4
11 8 13 6 |^. 42 |
h2. 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ă.
* 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
== include(page="template/taskfooter" task_id="fibosnek") ==
