== include(page="template/taskheader" task_id="fibosnek") ==
Poveste şi cerinţă...
Se consideră o matrice cu $n$ linii şi $m$ coloane ce conţine numere naturale nenule.
!{float: right; width: 350px; margin: 2px; }problema/fibosnek?fibosnek.png!
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.
Şirul numerelor Fibonacci este definit mai joş unde fib[k] reprezintă al k-lea număr Fibonacci:
* $fib[1] = 1, fib[2] = 1$
* $fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2$
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.
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
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 $fibosnek.in$ ...
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
În fişierul de ieşire $fibosnek.out$ ...
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$).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $c ∈ {1, 2}$
* $1 ≤ n, m ≤ 1 500$
* $Elementele matricei au valori ı̂n intervalul [1, 2^31^ − 1].$
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. Exemplu
h2. Exemple
table(example). |_. fibosnek.in |_. fibosnek.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 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$.
h3. Explicaţie
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ă.
== include(page="template/taskfooter" task_id="fibosnek") ==
== include(page="template/taskfooter" task_id="fibosnek") ==
