Fibosnek

fibosnek

== include(page="template/taskheader" task_id="fibosnek") ==

Se consideră o matrice cu $n$ linii şi $m$ coloane ce conţine numere naturale nenule.

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.

!{float: right; width: 350px; margin: 2px; }problema/fibosnek?fibosnek.png!

Şirul numerelor Fibonacci este definit mai joşunde fib[k] reprezintă al k-lea număr

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.

Fibonacci:
• fib[1] = 1, fib[2] = 1
• fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2

Şirul numerelor Fibonacci este definit mai joş unde fib[k] reprezintă al k-lea număr Fibonacci:

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.

* $fib[1] = 1, fib[2] = 1$
* $fib[k] = fib[k - 1] + fib[k - 2], pentru orice k > 2$

15311
28113
4298

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.

Figura 1: Exemplu de parcurgere snek a unei matrice cu 3 linii şi 4 coloane.

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

!problema/fibosnek?Poza.jpg!

h2. Cerinţe

Ordinea parcurgerii celulelor este:
1, 2, 4, 5, 8, 2, 3, 1, 9, 11, 13, 8
Numerele Fibonacci au fost evidenţiate.

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

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

# $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.$

h3. Cerinţe

h2. Date de intrare

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

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.

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.

h2. Date de ieşire

h3. Date de intrare

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

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. Restricţii

h3. Date de ieşire

* $c ∈ {1, 2}$
* $1 ≤ n, m ≤ 1 500$
* $Elementele matricei au valori ı̂n intervalul [1, 2^31^ − 1].$

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

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$ |

h4. Restricţii
• c ∈ {1, 2}
• 1 ≤ n, m ≤ 1 500
• Elementele matricei au valori ı̂n intervalul [1, 231 − 1].

h2. Exemple

Restricţii

table(example). |_. fibosnek.in |_. fibosnek.out |

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
 
| fibosnek.in | fibosnek.out |

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

4 2 9 8 |^. 9 |
| 2 3 4

4 2 9 8
2 3 4

1 5 3 11
2 8 1 13

4 2 9 8 |^. 61 |
| 2 4 4

4 2 9 8
2 4 4

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

11 8 13 6 |^. 42 |

11 8 13 6 | 9
61
42 |

h2. Explicaţii

h3. 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$.

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

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.

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") ==

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