Lista de probleme 3

Macarie a primit o nouă temă la informatică, având următorul enunț: Se consideră un șir de numere naturale nenule, A cu N elemente. Fie șirul crescător D format din toți divizorii naturali, nu neapărat distincți, ai elementelor din A. De exemplu, pentru N = 4 și A = (6,2,3,2), avem șirul D = (1,1,1,1,2,2,2,3,3,6). Cunoscându-se un șir Poz format din Q numere naturale nenule, reprezentând poziții din șirul D să se determine, pentru fiecare dintre acestea, elementul corespunzător din șirul D.

Se cunosc înălțimile a N vârfuri, plasate de la stânga la dreapta, în cadrul unui lanț muntos. Dacă plasăm o santinelă pe un vârf de o anumită înălțime, aceasta veghează vârful respectiv și maximum K vârfuri la stânga și maximum K vârfuri la dreapta acestuia, dar cu condiția ca înălțimile acestor vârfuri vegheate să fie mai mici sau egale cu înălțimea vârfului pe care se află santinela. Date fiind N, K și înălțimile celor N vârfuri, să se determine:

• Numărul maxim de vârfuri consecutive, începând de la primul vârf al lanțului muntos (inclusiv acest vârf), ce pot fi vegheate cu o singură santinelă.
• Numărul minim de santinele necesare ca toate vârfurile să fie vegheate.

David este mare zugrav și nu se duce nicăieri fără trafaletul său magic. El are la dispoziție o matrice A cu N linii și M coloane, care este colorată în alb și negru, asemenea unei table de șah. Fiecare celulă a matricei conține o valoare asociată. David vopsește o submatrice cu alb sau negru la alegere. Trafaletul adună automat (pentru că este magic) valorile din celulele vopsite care nu își schimbă culoarea, și scade valorile din celulele vopsite care își schimbă culoarea. Rezultatul acestui calcul este punctajul lui David. Cum David nu a reușit până acum să combine zugrăvitul și programarea, vă roagă pe voi să îl ajutați să obțină punctajul maxim!