Lista de probleme 10

Î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.

Mugurel a decis să devină în sfârșit cel mai mare antreprenor din Imperiul Rațelor de Cauciuc. Astfel, el și-a deschis o afacere cu fructele sale preferate: portocale și banane.

Acesta primește planul recoltelor de fructe: timp de N zile, în fiecare zi Mugurel primește M grămezi de portocale și M grămezi de banane (alternativ), reprezentate prin numărul lor de kilograme.
Mugurel trebuie să împacheteze toate aceste fructe, însă producătorul său de cutii îi oferă două variante, din care poate alege doar una: fabricarea a K cutii pentru portocale și K cutii pentru banane (împachetare separată), sau fabricarea a K cutii mixte (împachetarea portocalelor și a bananelor împreună).

Însă, totul are un preț. Fie \(c_{port}\), \(c_{ban}\), \(c_{mixt}\) capacitățile cutiilor de portocale, banane respectiv mixte. Atunci, Mugurel va plăti \(A \; maci \cdot c_{port} + B \; maci \cdot c_{ban}\) sau \(C \; maci \cdot c_{mixt}\), în funcție de varianta de împachetare aleasă, unde \(A\), \(B\) și \(C\) vor fi prețuri oferite de producător. Mugurel va alege metoda de împachetare astfel încât suma de bani cheltuită să fie cât mai mică.

După ce plătește și primește cutiile, începe împachetarea. De fiecare dată când închide o cutie, o pune la finalul șirului de cutii deja închise (Mugurel se ocupă mai întâi de grămada de portocale, apoi de cea de banane). La finalul împachetării fructelor, el trebuie să împartă șirul de cutii în două șiruri consecutive, pe care le vom numi loturi.

Loturile vor fi trimise către cele două cetăți ale Imperiului, însă Mugurel nu vrea să pornească un război între cele două cetăți, așadar vrea să le împartă cu grijă. Numim discrepanță a unui lot diferența dintre cutia cu număr maxim de kilograme și cea cu număr minim. Împărțirea trebuie făcută astfel încât suma discrepanțelor celor două loturi să fie minimă, pentru împachetare.

Cu atâtea responsabilități pe cap, Mugurel vă roagă să-l ajutați cu afacerea.

Alex, un mare entuziast al turismului, a decis să-și transforme pasiunea într-o afacere și să organizeze tururi ale orașului Bistrița. Orașul poate fi reprezentat ca un graf orientat al obiectivelor turistice, conectate direct de străzi. Totuși, dat fiind că abilitatea de a se orienta a lui Alex nu este comparabilă cu entuziasmul lui, organizarea traseelor este dificilă pentru el. În primul rând, el vrea să numere câte astfel de trasee există în oraș. Un traseu reprezintă o listă ordonată \(a\) de \(k\) obiective turistice, cu următoarele proprietăți:

• De la nodul \( {a}_{i} \) se poate ajunge în nodul \( {a}_{i+1} \)
• De la nodul \( {a}_{k} \) se poate ajunge în nodul \( {a}_{1} \)

Spunem că se poate ajunge de la nodul x la nodul y dacă există un drum de 0 sau mai multe străzi care începe în nodul x și se termină în nodul y. Există 2 tipuri de trasee turistice:

• Tipul 1, în care obiectivele se pot repeta
• Tipul 2, în care obiectivele trebuie să fie distincte

Graful obiectivelor turistice este un graf orientat în care o muchie de la x la y reprezintă un drum direct de la nodul x la nodul y. Alex are nevoie de ajutorul vostru, pentru a determina câte trasee de lungime k există pentru un tip dat de trasee turistice (Tipul 1 sau Tipul 2), pentru fiecare k de la 1 la Q.

România este formată din N orașe conectate între ele, existând un traseu unic între oricare două orașe. Un traseu este o secvență de drumuri care conectează două orașe, astfel încât niciun drum nu se repetă. În total, există N−1 drumuri bidirecționale care conectează orașele.

Fiecare drum are și un cost asociat. Echipa lui Jeffrey a creat o lista de M perechi de orașe între care se va circula foarte des pentru livrarea coletelor. Definim costul unei perechi de orașe (x, y) ca fiind suma costurilor drumurilor din traseul de la orașul x la orașul y. De asemenea, definim costul total ca fiind suma tuturor costurilor celor M perechi de orașe date.

Jeffrey poate să aplice următorul tip de operație: selectează un drum cu un cost strict pozitiv și îi scade costul cu 1. Din motive de “frugality”, această operație poate fi aplicată de cel mult K ori, unde K este un număr natural.

Se cere să găsiți costul total minim ce poate fi obținut, după aplicarea de cel mult K ori a operației menționate mai sus.

Se dă o matrice de mărime N pe N care conține litere ale alfabetului englez. Definim un drum dreapta-jos ca fiind un șir de celule ale matricei care începe cu celula (1, 1), se termină cu celula (N, N), iar pentru fiecare celulă (x, y) din drum (exceptând ultima), succesoarea sa este fie (x+1, y), fie (x, y+1). Spunem că șirul de caractere generat de un drum în matrice este șirul obținut prin concatenarea valorilor celulelor drumului în ordine.

Să se găsească 2 drumuri dreapta-jos care nu se intersectează (decât în celulele (1, 1) și (N, N)) pentru care coeficientul de similaritate este maxim. Coeficientul de similaritate a 2 drumuri reprezintă numărul de poziții i pentru care a[i] = b[i], 0 ≤ i < lungime(a), lungime(b), unde a și b sunt șirurile generate de cele 2 drumuri.