Lista de probleme 7

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3759 Cartita

În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de h[i] centimetri. Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță.

#3778 Pian

Ian este un copil pasionat de muzică, așa că părinții săi i-au cumpărat de ziua lui un pian. Pianul lui Ian este mai special, acesta are N clape. Întrucât pianul nu este nou, clapele se mișcă mai greu, astfel apăsarea celei de-a i-a clape durează t[i] secunde. Deoarece Ian este foarte nerăbdător, s-a hotarât să repare clapele pianului pentru ca apăsarea unei clape să fie cât mai rapidă. Acesta poate selecta două clape vecine i și i+1 ce necesită t[i], respectiv t[i+1] secunde pentru a fi apăsate și le lustruiește. În urma lustruirii, cele două clape vor necesita doar cmmdc(t[i],t[i+1]) secunde pentru apăsarea fiecăreia. Practic, o operație va efectua următoarea transformare asupra clapelor: t[i] = t[i + 1] = cmmdc(t[i], t[i+1]).

  • Cerința 1: Ian vrea să facă un riff (adică să apese fiecare clapă o singură dată) și vrea să știe care ar fi durata de timp a unui riff pe pianul lustruit.
  • Cerința 2: Pentru că Ian nu are timp de pierdut cu lustruitul, acesta vrea o listă de instrucțiuni de lungime minimă asfel încât dupa efectuarea instrucțiunilor pianul să fie lustruit.

Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x , y ≤ n. Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x , y]?”.

Se dă un vector indexat de la 1 cu n elemente numere naturale. Să se răspundă la q întrebări de forma x y, cu semnificația: “Care este cel mai mare divizor comun al elementelor cu indici cuprinși între x și y, inclusiv?”

#3692 maxime

Se dă un șir V cu N valori naturale nenule, memorate pe poziții consecutive începând cu poziția 1. Notăm cu S următoarea secvență de cod aplicată asupra sa:

(C/C++)
maxim = 0;
rep = 0;
for(i = 1; i <= N; i++)
	if(V[i] > maxim)
		maxim = V[i];
	else
		if(V[i] == maxim)
			rep++;

Considerăm operația de eliminare din V a elementului de pe o anumită poziție dată P. În urma operației de eliminare elementele de pe pozițiile P + 1, P + 2, ..., N ajung pe o poziție cu 1 mai mică iar N scade cu 1.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei rep dacă am aplica secvența S asupra șirului obținut după fiecare operație de eliminare.

Undeva, într-un ținut îndepărtat, își desfășoară activitatea o vestită companie, mai exact Mondial Computers SRL. Aceștia lucrează cu mulți clienți de renume, deci au nevoie de multă forță de muncă. Astfel, ei au o bază de date în care mențin informații despre angajații lor, dar, recent, echipa care se ocupa de această bază de date a dat dovadă de un randament scăzut, iar ca urmare a acestui fapt, manager-ul general a decis, fără a ține cont de consecințe, să îi concedieze, iar aceștia, de supărare, au șters înainte de a pleca din companie toate datele angajaților. Acum manager-ul are nevoie de ajutorul vostru(voluntar, desigur) pentru reorganizarea acestei baze de date până reușește să angajeze noi oameni.

Se dă un şir cu n elemente, numere naturale. Aflaţi câte secvenţe din şir au lungimea mai mare decât minimul elementelor din secvenţă.