Lista de probleme 3

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.