Lista de probleme 888

Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și interogarea unui interval de indici (determinarea celei mai mici valori aflate între cei doi indici, inclusiv).
Afișați răspunsul la fiecare interogare.

Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui interval (schimbarea valorii tuturor elementelor aflate între două poziții date) și interogarea unui interval (determinarea celei mai mici valori aflate între două poziții date).

Jany MooRANDy este șeful valutei peste țara sa MORANDIA. Pentru a-și tachina dușmanii, el a declarat următoarele: “Să bată vântul și ploaia, eu fac bani și-n Himalaya! Unde fac eu bani pachete, dușmanii culeg doar pietre!”. Pentru a le dovedi acestea, el a mers în munții Himalaya. Aceștia sunt alcătuiți din N vârfuri, vârful i având înălțimea H[i]. El va construi o telecabină ce va porni din vârful 1 și va ajunge în vârful N. Cabina va avea K puncte de oprire (un punct de oprire este considerat un vârf) unde dușmanii săi vor culege pietre. Fie două puncte de oprire consecutive i și j (i < j). Dacă H[i] ≤ H[j] atunci dușmanii vor plăti (H[j] - H[i]) * C1, altfel (H[i] - H[j]) * C2.

Se consideră un șir cu n numere naturale. Determinați cel mai lung subșir crescător al șirului, cu proprietatea că toate elementele subșirului sunt numere prime. Dacă există mai multe subșiruri de lungime maximă se va afișa subșirul minim lexicografic.

Șcuțu, elev pe clasa a 10-a, s-a plictisit să lucreze probleme de clasa a 6-a. Mygo a văzut că Șcuțu a reușit să obțină 100p pe problema Munte de la OJI2014, însă nu cu o soluție prea inteligentă, așa că îi va pune o provocare. Se dă un vector A de N elemente indexat de la 1. Un vârf este un element A[i] cu proprietatea că A[i-1] < A[i] > A[i+1] (1 < i < N). Mygo îi oferă lui Șcuțu Q operații de tipul:

• 1 x y: “Elementul de pe poziția x ia valoarea y”.
• 2 x y: “Având o copie a vectorului A[x...y] (ceea ce urmează nu va afecta cu nimic vectorul A), se determină toate vârfurile iar acestea se elimină, procedeul acesta continuă până când nu vor mai exista vârfuri. Se cere să se afișeze câte vârfuri au existat de la început până la final”.

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

Alex se află în sistemul de coordonate 2D. Aflându-se în coordonatele (x, y), el primește un număr aleator între 1 și 2 (50% șanse să primească 1 și 50% șanse să primească 2). Dacă acest număr este 1, atunci el se va deplasa în (x + 1, y), altfel în (x, y + 1).

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.

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.

Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.

Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,A[N].