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 jos de la elementul aflat pe prima linie, până la cel aflat pe ultima linie, ca în exemplu.

Șirul numerelor Fibonacci este definit mai jos unde $\text{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 \gt 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 și precizări

• $c \in \{1, 2\}$;
• $1 \leq n, m \leq 1 \ 500$;
• Elementele matricei au valori în intervalul $[1, 2^{31}-1]$;
• Pentru $21$ de puncte, $c = 1$ și $n, m \leq 1 \ 000$;
• Pentru $20$ de puncte, $c = 2$ și $n, m \leq 100$;
• Pentru $44$ de puncte, $c = 2$ și $n, m \leq 1 \ 000$;
• Pentru $15$ puncte, $c = 2$ și nu există restricții suplimentare.

Exemplul 1

fibosnek.in

1 3 4
1 5 3 11
2 8 1 13
4 2 9 8

fibosnek.out

9

Explicație

$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

fibosnek.in

2 3 4
1 5 3 11
2 8 1 13
4 2 9 8

fibosnek.out

61

Explicație

$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

fibosnek.in

2 4 4
2 4 7 1
3 3 6 7
5 5 8 4
11 8 13 6

fibosnek.out

42

Explicație

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