Lista de probleme 3

Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m.
Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1, h[i]] și în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordine crescătoare (h[i-1] ≤ h[i], 1 ≤ i ≤ n).
Să se răspundă la q întrebări de forma: dându-se numerele A, B, C, D se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colțul stânga-jos în coloana A și linia B, iar colțul dreapta-sus în coloana C și linia D.

Corina a cumpărat de la magazin un material din pânză colorată, de formă dreptunghiulară pentru a decupa din el o față de masă pentru masa din bucătărie. Fiindcă este pasionată de șah, Corina a ales un material format din n x m pătrate de aceeași dimensiune colorate cu alb sau negru. Pătratele sunt lipite și sunt dispuse pe linii și coloane paralele cu laturile dreptunghiului din pânză care a fost cumpărat. Două pătrate se numesc vecine dacă au în comun o latură. Materialul din pânză nu respectă neapărat structura unei table de șah, adică pătratele vecine pe aceeași linie sau pe aceeași coloană nu sunt în mod necesar colorate în mod alternativ.
Corina își propune prin urmare să decupeze un dreptunghi cu un număr maxim de pătrate, paralel cu laturile dreptunghiului din pânză care a fost cumpărat, care să respecte alternanța culorilor pe o tablă de șah.
Să se determine numărul maxim de pătrate întregi ale unui dreptunghi cu laturile paralele cu cele ale materialului cumpărat, care poate fi decupat astfel încât să nu existe două pătrate vecine având aceeași culoare.

Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt n cartonașe. Pe fiecare cartonaș este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonașe sunt distincte între ele.
Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaș din cutie și apoi determină valoarea magică asociată numărului natural scris pe cartonaș. Pentru fiecare cartonaș valoarea magică este dată de al k-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obținute pentru cele n cartonașe și apoi să introducă în ordine cifrele valorii obținute, pentru a descuia lada. Deoarece vrăjitoarea nu are timp la dispoziție vă roagă pe voi să o ajutați să rezolve următoarele probleme:
1. Să afle valoarea magică pentru un cartonaș dat;
2. Să afle cifrul cufărului.