Lista de probleme 3

Se consideră o matrice A având N linii și N coloane. Elementele acesteia aparțin mulțimii {0,1,2}. Pe fiecare linie și pe fiecare coloană valorile elementelor sunt dispuse crescător.

Fie două elemente din matrice situate pe linia i1 și coloana j1 respectiv i2 și j2,unde i1≤i2 și j1≤j2. O submatrice a lui A, având colțurile stânga-sus şi dreapta-jos în (i1,j1) și (i2,j2), este formată din toate elementele situate pe linii cuprinse între i1 și i2, inclusiv, și coloane între j1 și j2, inclusiv. Numim submatrice constantă o submatrice a matricei A, având toate elementele egale.

Realizați un program care determină numărul maxim K de elemente pe care îl are o submatrice constantă a lui A și numărul submatricilor constante formate din K elemente.

În timpul activităților din “Săptămâna Altfel” elevii clasei a VII-a doresc să ajute la organizarea cărților din biblioteca școlii. Fiecare carte este etichetată cu un cod care este exprimat printr-un un șir de caractere distincte. Acestea pot fi cifrele 0, 1,..,9 și primele zece litere mici ale alfabetului englez a, b,..,j. Codul identifică în mod unic fiecare carte, adică nu vor exista două cărți cu același cod, dar şi genul literar din care acestea face parte. Cărțile din acelaşi gen literar au codul de identificare format din aceleaşi caractere, distincte, dispuse în altă ordine.

Numim coduri pereche două coduri de identificare care au același număr de caractere și care diferă printr-un
caracter. De exemplu, codurile 42a8 și 2c8a sunt coduri pereche. Pe de altă parte, codurile 42a8 și 248a,
respectiv 42ab și 248c, nu sunt coduri pereche.

Fiind dat șirul celor N coduri de identificare, scrieţi un program care să rezolve următoarele cerinţe:

1. determină numărul de cărți din cel mai numeros gen literar și numărul de genuri literare care au acest număr maxim de cărți.
2. determină numărul de coduri, din șirul celor N, care sunt coduri pereche cu ultimul cod din șir

Scrat și Scratte sunt două veverițe devoratoare de ghinde. Ele trăiesc într-un stejar înalt și culeg ghinde din cele N ramuri ale acestuia. Veverițele vor organiza un concurs: cine culege cele mai multe ghinde în K ture. Într-o tură,
fiecare veveriță se va deplasa de la vizuină până la o ramură a stejarului, de unde va culege cât mai multe ghinde, dar
nu mai mult de M ghinde, după care va reveni în vizuină. Veverițele vor efectua alternativ fiecare câte K ture, prima
care începe fiind Scratte.

Supărat că la concurs nu va începe primul, Scrat decide să se antreneze separat și să vadă câte ghinde ar culege în K
ture, dacă ar fi singur

Să se realizeze un program care determină:

1. Câte ghinde culege Scrat în timpul antrenamentului;
2. Câte ghinde a cules fiecare veveriță pe durata concursului.