Lista de probleme 6

La grădinița din orașul Matrix, copiii se joacă folosind matrici pătratice în loc de mașinuțe sau păpuși. Axel, fiind un copil foarte bun la informatică, s-a gândit să le propună colegilor un joc cel puțin interesant.
Acesta le oferă un număr natural N și apoi o matrice cu N linii şi N coloane, numerotate de la 1 la N. Matricea conţine numere naturale nenule. Asupra matricei se poate aplica un singur tip de operație, de oricâte ori:

• Se alege un număr i, cuprins între 1 şi N;
• Se permută circular în sus cu o poziţie elementele coloanei i.

Deoarece colegii lui Axel sunt totuși prea mici pentru a ști să rezolve astfel de probleme, aceștia vă cer ajutorul și vă roagă să rezolvați problema, oferindu-vă în schimb 100 de puncte.

Legenda spune că există o Matrice cu N linii şi M coloane. O celulă va fi identificată prin linia şi coloana pe care se află. Această Matrice mistică are inițial în toate celulele valoarea 0. Asupra Matricei poţi efectua Q transformări. La o transformare, atingi o celulă (i,j), iar Matricea te va întreba (da, Legenda spune că Matricea vorbește): “Ce valoare vrei să aduni, maestre?”. Dacă tu răspunzi x, atunci Matricea mistică va construi un triunghi dreptunghic isoscel cu unghiul drept în celula (i,j), celelalte colţuri fiind în celulele (i-x+1, j), respectiv (i,j-x+1). Date fiind N, M, Q reprezentând numărul de linii, numărul de coloane, respectiv numărul de transformări, precum şi cele Q transformări efectuate, să se determine Matricea după efectuarea celor Q transformări.

Se consideră N numere naturale nenule a1, a2, …, aN. Să se determine numărul de perechi de indici (i,j), 1 ≤ i, j ≤ N, i ≠ j , cu proprietatea că, dacă am alipi numărul aj la finalul numărului ai, obținem un număr divizibil cu 11. Perechile (i,j) și (j,i) se consideră diferite.

Dându-se un șir A de N numere naturale nenule numerotate de la 1 la N, să se determine câte subsecvențe [L,R] cu 1 < L ≤ R < N există, astfel încât elementele A[L], A[L+1],…, A[R] să fie strict mai mari decât elementele A[L-1] și A[R+1]. De asemenea, se cere și determinarea lungimii maxime a unei astfel de secvențe. Scrieți un program care să rezolve următoarele două cerințe:
1) Să se determine lungimea maximă a unei subsecvențe ce respectă proprietatea din enunț;
2) Să se determine numărul de subsecvențe ce respectă proprietatea din enunț.

Cunoscându-se N și M, dimensiunile satului, C numărul cailor, forțele inițiale ale cailor și matricile a și p, să se determine numărul de cai pe care Lică îi poate utiliza astfel încât el să reușească să traverseze satul, de la casa lui până la ieșirea din sat.

Aflându-se la moșia lui Pascalopol, Otilia este fascinată de vasta întindere de pământ pe care bărbatul o deține. Cum Pascalopol este un om darnic și îi face toate poftele Otiliei, încă de când era mică, acesta îi dăruiește tinerei o bucată de pământ de dimensiune N*M împărțită în parcele de dimensiune 1*1, dispuse pe N linii și M coloane (numerotate de la 1 la N, respectiv de la 1 la M). Pentru că Felix este gelos pe Pascalopol și nu suportă ca Otilia să-i ofere atât de multă atenție, tânărul i-a pus următoarea întrebare moșierului, vrând prin aceasta să-i arate că el este net superior din punct de vedere informatic:

“- Dacă eu plec din parcela (1,1), iar calul meu poate face un salt cu orice lungime între 1 și K la sud (linia crește) sau la est (coloana crește), în câte moduri pot ajunge în parcela (L,C), ținând cont că nu pot păși pe o parcelă care conține o groapă.”. Pentru că numărul poate fi foarte mare, Felix se mulțumește doar cu restul acestuia la împărțirea cu 1.000.000.007.Cum Pascalopol nu le are cu calculatoarele, iar aceasta este clar o problemă de Informatică, moșierul vă cere ajutorul și vă va oferi în schimb 100 de puncte.