Lista de probleme 6

În fiecare zi, cei 7 pitici lucrează cu spor în mina lor, pentru a colecta cât mai multe diamante. Mina poate fi reprezentată ca o matrice pătratică cu latura N, în fiecare element al matricei aflându-se un număr cunoscut de diamante. Piticii au cumpărat o mașinărie specială, care să le faciliteze munca. Cu ajutorul acesteia, se pot colecta diamante în două moduri. Primul mod, denumit colectare principală, presupune colectarea diamantelor de pe K diagonale învecinate, paralele cu diagonala principală a matricei; al doilea mod, denumit colectare secundară, presupune colectarea diamantelor aflate pe K diagonale învecinate, paralele cu diagonala secundară a matricei. Piticii pot folosi aparatul o singură dată pentru un tip de colectare. În urma unei colectări, elementele afectate de aceasta nu mai conțin diamante.

Deoarece încă nu știu să folosească mașinăria la capacitate maximă, piticii au nevoie de ajutorul tău!

Scrieți un program care să-i ajute pe pitici, determinând:

1) Numărul maxim de diamante care pot fi colectate în urma unei colectări principale.
2) Numărul maxim de diamante care pot fi colectate în urma unei colectări secundare.
3) Numărul maxim de diamante pe care piticii le pot colecta din mină.

Medicii de la Institutul Inimii doresc să calculeze puterea maximă a inimii unui pacient, utilizând măsurători făcute cu aparate electronice.

Se dau n numere naturale, reprezentând intensitățile bătăilor unei inimi la intervale de o secundă. Intensitățile pot fi vizualizate ca n linii verticale de înălțimi \({h}_{1}, {h}_{2}, … {h}_{n}\). Distanța dintre două linii consecutive este 1.

Puterea maximă a unei inimi se definește ca fiind aria maximă a unui dreptunghi care se poate obține între două bătăi oarecare ale inimii.

Cunoscând numărul n de bătăi ale inimii unui pacient și intensitățile acestora \({h}_{1}, {h}_{2}, … {h}_{n}\), determinați puterea maximă a inimii.

Gigel participă la un concurs de matematică și informatică și îi plac foarte mult numerele prime și secvențele.

Tocmai a găsit un șir cu N elemente numere naturale și un număr K. Dezamăgit că nu toate elementele șirului sunt prime, Gigel vrea să afle care este cea mai lungă secvență din șir care conține cel mult K elemente neprime.

Scrieți un program care să determine cea mai lungă secvență de elemente din șir care conține cel mult K numere neprime.

Scrieți un program care citește numărul de elevi și notele acestora și determină numărul minim de grupe în care pot fi împărțiți elevii conform regulii descrise în enunț.

Roxana găsește noul șir \(v\) și vă adresează o întrebare: câte perechi de indici \((a, b)\), unde \(1 \le a \le b \le N\), există, cu proprietatea că suma \(xor\) a elementelor \({v}_{i}\), cu \(a \le i \le b\), este \(0\)?

Andino și-a găsit o nouă pasiune – muzica. După cum se spune, munca întotdeauna dă roade, așa că iată-l la primul lui concert! Andino, fiind un artist care a devenit popular foarte rapid, a adunat un public numeros la concertul lui, dispus sub forma unei matrice cu N linii și M coloane.

Fiecare fan al lui Andino poate avea una din cele două stări: pe vibe, codificată în structura matricei cu 1 și pe plictiseală, codificată în structura matricei cu 0. Andino a observat asta prin mulțime și dorește să schimbe starea oamenilor, așa că ia următoarea decizie: de-a lungul concertului său, Andino schimbă vibe-ul fanilor lui situați într-o submatrice definită prin colțul stânga-sus de coordonate (x1,y1) și, respectiv, prin colțul dreapta-jos de coordonate (x2,y2).

Prin schimbă vibe-ul înțelegem că starea oricărui fan se schimbă (starea devine pe vibe din pe plictiseală și vice-versa). Pe toată durata concertului, Andino schimbă vibe-ul fanilor săi de exact T ori.

La finalul concertului, Andino vrea să știe cum s-a simțit lumea la concert și îi întreabă pe Q dintre fanii săi care e starea lor. O întrebare are următoarea formă: „Care este starea fanului de coordonata xQ,yQ?”. Fiind ocupat, Andino vă roagă pe voi să-l ajutați să obțină răspunsurile la aceste întrebări.