Lista de probleme 6

Se consideră aranjamentul piramidal de numere cunoscut și sub denumirea de triunghiul lui Pascal. În vârful și pe marginile laterale ale piramidei se află numărul 1. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra. Definim un tripas(r,c,L) ca fiind un triunghi echilateral de numere din interiorul triunghiului lui Pascal, pentru care se precizează poziția (r, c) a vârfului și L, lungimea laturii (r=rând, c=coloană, L=lungime latură). Exemplu: tripas(3,1,4) – reprezintă triunghiul de numere cu vârful poziționat pe rândul al treilea, primul element și care are lungimea laturii de 4 elemente, adică numerele (1), (1,3), (1,4,6), (1,5,10,10) – scrise de sus în jos și de la stânga la dreapta. Pe figura de mai sus, tripas(3,1,4) are elementele încadrate în dreptunghiuri. Notăm cu S suma elementelor unui tripas(r,c,L).

Alecu este un copil năzdrăvan care strică orice lucru. El a scris pe o foaie de hârtie un cuvânt. Fiind elev în clasa întâi, el nu a învățat decât primele X litere mici ale alfabetului englez, iar cuvântul de pe foaie este scris doar cu aceste litere.

El își propune să taie foaia în mai multe bucăți dar să obțină doar cuvinte având același număr de litere și în același timp toate cuvintele obținute în urma tăierii să fie palindromuri. Un cuvânt este palindrom dacă citit de la stânga spre dreapta este identic cu cuvântul obținut prin citire de la dreapta spre stânga. Exemplu de palindrom este cuvântul abcba.

În dorința de a obține în urma tăierii doar cuvinte palindrom, Alecu poate schimba orice literă a cuvântului, în oricare alta cunoscută de el, dar fiecare astfel de schimbare are un cost cunoscut. Mai mult, el știe că o literă din cuvântul inițial nu o poate schimba decât cel mult o singură dată.

Notăm cu Nr(c) numărul minim de palindromuri de lungimi egale în care poate fi tăiat cuvântul de pe foaie, având voie să se efectueze schimbări ale literelor, dar care să nu însumeze un cost total mai mare decât c. Alecu știe să determine valoarea Nr(c) pentru orice număr natural c.

Scrieți un program care pentru un număr natural Q și șirul numerelor naturale 0,1,2,...,Q-1,Q, determină suma: Nr(0)+Nr(1)+Nr(2)+...+ Nr(Q-1)+Nr(Q).

Ion este un tânăr muzician și studiază chitara clasică. La un spectacol în aer liber, Ion a fost invitat să interpreteze câteva dintre piesele sale. Ion are în repertoriu n piese, a căror durată este t[1], t[2], …, t[n] și ştie că timpul care-i va fi alocat nu poate depăşi T unităţi de timp. Pentru alegerea pieselor, Ion este interesat să ştie câte variante distincte are de a interpreta cel puţin o piesă în spectacol, astfel încât durata totală a pieselor interpretate să nu depăşească T. Două variante sunt distincte dacă există cel puţin o melodie care se găseşte într-o variantă şi nu se găseşte în cealaltă variantă. Cunoscând n, T și duratele pieselor, determinaţi numărul de variante distincte pe care le are Ion de a interpreta piese astfel încât durata lor să nu depăşească T.

Se consideră o tablă de șah sub forma unei matrice cu M linii si N coloane conținând caracterele '.' si '#'. Celulele care conțin '#' sunt considerate interzise și nu se pot așeza turnuri în ele. Celulele interzise nu blochează atacurile turnurilor. Să se calculeze X, numărul de posibilități de a așeza turnuri în celulele neinterzise, astfel încât să nu existe doua turnuri așezate pe aceeași linie sau pe aceeași coloana. Deoarece acest număr poate fi foarte mare, se va determina X modulo 1000003.

Un spărgător care doreşte să golească un seif are nevoie de codul acestuia şi pentru aceasta are deja o secvenţă de K numere naturale care reprezintă în mod cert o parte din cod, care din păcate nu este obligatoriu complet. El primeşte de la doi asociaţi câte o secvenţă de M respectiv N numere naturale, care, spune fiecare din ei, este codul corect şi complet. Pentru că cele două coduri nu coincid, spărgătorul, pentru a-şi maximiza şansele, încearcă să determine un cod cât mai lung, format dintr-un şir de numere care este comun celor două şiruri primite de la asociaţi şi, în plus, să conţină ca subşir codul său. Dat un şir de numere naturale c[1],c[2],...,c[K] ce reprezintă codul spărgătorului, precum şi alte două şiruri de numere naturale x[1],x[2],...,x[M] şi y[1],y[2],...,y[N], ce reprezintă codurile celor doi asociaţi, să se determine lungimea maximă a unui şir de numere care este cod comun celor două coduri ale asociaţilor şi conţine, în plus, ca subşir codul spărgătorului.

Aventura robotului Curiosity pe Marte continuă. Robotul se deplasează de-a lungul unei axe de coordonate Ox. Punctul de plecare în incursiune are coordonata x=0, iar punctul unde este finalizat studiul are coordonata Xf. Robotul se deplasează cu viteză constantă și parcurge o unitate de drum într-o unitate de timp.

Cercetătorii au stabilit N zone ce fac posibilă recepția datelor transmise de robot către satelit. Fiecare zonă este definită prin pereche X[i] L[i] (X[i] – coordonata de început a zonei i, L[i] – lungimea zonei). Zonele nu interferează (nu au puncte comune). Datele sunt transmise în pachete de dimensiune fixă, iar durata de transmisie a unui pachet este D.

Pe parcursul unei zone robotul poate transmite unul sau mai multe pachete de date. După ce a finalizat transmisia unui pachet, robotul poate continua transmisia unui alt pachet, dacă este posibil (nu este acceptată transmiterea unui pachet incomplet), sau poate întrerupe transmisia. După întrerupere, robotul poate relua transmisia după cel puțin de T unității de timp consumate.

Să se determine numărul maxim de pachete de date ce pot fi transmise de către robot satelitului.