Fişierul intrare/ieşire:	fibosnek.in, fibosnek.out	Sursă	OJI 2023, clasa a 9-a
Autor	Eugen Nodea	Adăugată de	Moldovan Laura •laura2020
Timp execuţie pe test	0.15 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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, fib² = 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).

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.

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.

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

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?