== include(page="template/taskheader" task_id="fibosnek") ==
Se consideră o matrice cu $n$ linii şi $m$ coloane ce conţine numere naturale nenule.
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.
!{float: right; width: 350px; margin: 2px; }problema/fibosnek?fibosnek.png!
Şirul numerelor Fibonacci este definit mai joş unde fib[k] reprezintă al k-lea număr
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.
Fibonacci:
• fib[1] = 1, fib[2] = 1
• fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2
Şirul numerelor Fibonacci este definit mai joş unde fib[k] reprezintă al k-lea număr Fibonacci:
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.
* $fib[1] = 1, fib[2] = 1$
* $fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2$
15311
28113
4298
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.
Figura 1: Exemplu de parcurgere snek a unei matrice cu 3 linii şi 4 coloane.
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)$.
!problema/fibosnek?Poza.jpg!
Ordinea parcurgerii celulelor este:
1, 2, 4, 5, 8, 2, 3, 1, 9, 11, 13, 8
Numerele Fibonacci au fost evidenţiate.
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. Cerinţe
Fiind date elementele matricei cu $n$ linii şi $m$ coloane să se determine:
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.$
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.
h2. Date de intrare
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.
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 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$).
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$ |
• c ∈ {1, 2}
• 1 ≤ n, m ≤ 1 500
• Elementele matricei au valori ı̂n intervalul [1, 231 − 1].
| # | 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 |
| fibosnek.in | fibosnek.out |
| 1 3 4
1 5 3 11
2 8 1 13
4 2 9 8 |^. 9 |
4 2 9 8 | 9 |
| 2 3 4
1 5 3 11
2 8 1 13
4 2 9 8 |^. 61 |
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 |
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$.
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$.
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ă.
== include(page="template/taskfooter" task_id="fibosnek") ==
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ă.
