Lista de probleme 3

Mihai s-a decis în sfârșit să compună o melodie. Fără să știe de unde să înceapă, a scris pe o foaie n note muzicale. Fiecare notă muzicală este definită de două valori reprezentând durata și înălțimea acesteia. Dându-se n note sub forma a n perechi de numere, x și y, să se afișeze scorul maxim ce poate fi obținut după gruparea tuturor notelor date în grupuri disjuncte.

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

Dându-se n cufere, care conțin obiectele în ordinea inițială, Alex vă roagă să realizați un program care să determine:

• pentru fiecare etichetă distinctă de obiect întâlnit în cele n cufere, numărul total al obiectelor cu acea etichetă;
• noile etichete ale compartimentelor care compun cele n cufere, după rearanjarea obiectelor.