Lista de probleme 10

Fiind data harta grădinii se cere să se determine starea finală a iepuraşului (îngeraş, rătăcit respectiv fericit), numărul de morcovi ronţăiţi până în momentul terminării expediţiei, precum şi numărul de paşi pe care îi face iepuraşul până la acest moment.

Ana a descoperit că are o adevărată pasiune pentru palindromuri. Un şir de numere este palindrom dacă se citeşte la fel de la stânga la dreapta şi de la dreapta la stânga (primul număr este egal cu ultimul, al doilea cu penultimul etc). Ea are un şir cu N numere naturale şi vrea ca orice subsecvenţă de lungime impară a şirului să fie palindrom. Pentru a-şi îndeplini dorinţa ea poate efectua asupra şirului mai multe operaţii. O operaţie constă în alegerea unui element din şir şi incrementarea sau decrementarea lui cu o unitate. Bineînţeles, Ana doreşte să utilizeze un număr minim de operaţii pentru ca şirul obţinut să respecte proprietatea amintită mai sus (orice subsecvenţă de lungime impară să fie palindrom).

Să se determine numărul de secvenţe PM care conţin x semne plus şi y semne minus.

Se consideră o matrice A cu următoarele proprietăţi:

• conţine n linii şi m coloane;
• conţine doar valorile 0 şi 1;
• pe fiecare linie valorile sunt plasate în ordine crescătoare.

Definim o submatrice determinată de perechea de linii L1 şi L2 (L1 ≤ L2) şi de perechea de coloane C1 şi C2 (C1 ≤ C2) ca fiind totalitatea elementelor matricei A[i,j] pentru care L1 ≤ i ≤ L2 şi C1 ≤ j ≤ C2.
Dacă toate elementele unei submatrice sunt egale cu 0, atunci submatricea se numeşte nulă.
Asupra matricei A putem efectua una sau mai multe operaţii de interschimbări de linii. Prin astfel de interschimbări liniile matricei pot fi rearanjate astfel încât matricea A să conţină cel puţin o submatrice nulă cu număr maxim de elemente.
Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.

Se consideră o autostradă dispusă în linie dreaptă având N puncte de acces (intrare şi ieşire). În fiecare punct de acces există containere pentru colectarea deşeurilor, toate containerele au aceeaşi capacitate şi în fiecare punct de acces pot fi mai multe astfel de containere. Firma care asigură curăţenia dispune de un singur mijloc de transport al containerelor. Acest mijloc de transport poate încărca exact un număr K de containere. Accesul mijlocului de transport pe autostradă se face cu restricţii pentru a nu perturba traficul şi din acest motiv trebuie ca la fiecare acces pe autostradă să fie colectate exact atâtea containere cât este capacitatea maşinii, dar dintr-un punct de colectare trebuie să ia exact un container, deci dacă se intră pe autostradă la punctul de acces P, unde P≤N-K+1, atunci trebuie să ia containere de la punctele de acces numerotate cu P, P+1, P+2,…, P+K-1, în aceste puncte de acces scade cu 1 numărul containerelor rămase. Firma trebuie să găsească toate valorile posibile pentru K astfel încât să poată colecta toate containerele.

Se cere să se găsească toate valorile posibile pentru K astfel încât să fie adunate toate containerele.

Alina este mare iubitoare de teatru. Directorul teatrului i-a oferit șansa să joace în mai multe spectacole, ca figurant, deocamdată. Costumiera de scenă a decis să-i dea C costume diferite dintre cele care sunt destinate acestei stagiuni. Alina va duce costumele acasă și le va ajusta ca să-i vină bine. Stagiunea durează Z zile consecutive și în fiecare zi se joacă câte o piesă. Aceeași piesă se va juca, desigur în una sau mai mai multe zile ale stagiunii. Fiecărei piese i se asociază un unic costum de figurant, deci pentru fiecare piesă în care joacă, Alina trebuie să îmbrace un singur costum, acela asociat piesei respective. Costumele de figuranți sunt identificate prin literele mari ale alfabetului englez: A, B, C, …, X, Y, Z. Alina are voie să-și aleagă cele C costume diferite.

Cunoscând costumul asociat fiecărei zile a stagiunii, ajutați-o pe Alina să-și aleagă cele C costume diferite, în așa fel încât să poată juca într-un număr cât mai mare de piese consecutive.

Se consideră şirul de numere naturale:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21,...

Se grupează numerele din şir astfel încât prima grupă, numerotată cu 1, este formată din primul număr din şir (1), a doua grupă, numerotată cu 2, este formată din următoarele două numere din şir (3,5), a treia grupă, numerotată cu 3, este formată din următoarele trei numere din şir (7,9,11),…, a n-a grupă din şir, numerotată cu n, este formată din următoarele n numere din şir, etc.

Deduceţi regula după care sunt generaţi termenii şirului şi scrieţi un program care să citească numerele naturale p, n şi k şi care să determine:

a) al câtelea număr din şir are valoarea p;
b) cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele tuturor numerelor din grupa a n-a a şirului dat, nu neapărat toate aceste cifre;
c) numărul grupei cu proprietatea că suma tuturor numerelor conţinute de aceasta este egală cu numărul k, dacă există o astfel de grupă.

Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel:
1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește.
Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.
Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.

Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

Harta Galaxiei este reprezentată ca o matrice cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). Orice element al matricei reprezintă o zonă de formă pătrată cu latura de 1 an lumină (denumită quadrant) şi poate fi identificat prin coordonatele sale (numărul liniei şi respectiv numărul coloanei pe care află).

Nava Enterprise se află într-un quadrant de coordonate cunoscute şi trebuie să ajungă la destinaţie (un alt quadrant, diferit de cel de plecare, de coordonate de asemenea cunoscute).

Nava se poate deplasa de la un quadrant la unul dintre cei învecinaţi pe orizontală sau verticală într-o unitate de timp (mai exact, din zona de coordonate (L,C) nava se poate deplasa în una dintre zonele de coordonate (L-1,C), (L+1,C), (L,C-1), (L,C+1), fără a ieşi de pe hartă).

În plus, în unele zone (quadranţi) se găsesc porţi stelare. O poartă stelară permite deplasarea navei într-o unitate de timp în oricare altă zonă în care se găseşte o altă poartă stelară. Dacă în drumul său nava ajunge într-o zonă cu o poartă stelară, nava se poate deplasa într-o altă zonă cu poartă stelară sau poate să-şi continue drumul în una dintre zonele învecinate.

Determinați timpul minim în care nava poate ajunge din zona inițială în cea finală, precum și numărul de trasee de durată minimă.