== include(page="template/taskheader" task_id="fibosnek") ==
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).
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 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.
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
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 $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
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 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") ==
