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

h3. Cerinţe

h2. Cerinţe

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

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.

h3. Date de intrare

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.

h3. Date de ieşire

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

• 1 ≤ n, m ≤ 1 500
• Elementele matricei au valori ı̂n intervalul [1, 231 − 1].

Restricţii

h2. Restricţii

121c = 1 şi n, m ≤ 1 000
220c = 2 şi n, m ≤ 100
344c = 2 şi n, m ≤ 1 000
415c = 2 şi fără alte restricţii suplimentare

Exemple

h2. Exemple

| fibosnek.in | fibosnek.out |
| 1 3 4

61
42 |

h3. Explicaţii

h2. Explicaţii

h4.Exemplul 1

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.