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

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

Cerinţe

Fiind date elementele matricei cu n linii şi m coloane să se determine:

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.

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.

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

Restricţii

• c ∈ {1, 2}
• 1 ≤ n, m ≤ 1 500
• Elementele matricei au valori ı̂n intervalul [1, 2³¹ − 1].

Exemple

Explicaţii

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.

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.

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

Cum se trimit solutii?