Lista de probleme 892

Se dau N segmente în plan, fiecare fiind paralel cu una dintre axele de coordonate. Determinați numărul total de puncte de intersecție între două segmente.

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 celui mai mare divizor comun pentru valorile aflate între cei doi indici, inclusiv).

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 determinarea, urmată de ștergerea, elementului minim. Dacă valoarea minimă apare de mai multe ori în șir, se elimină prima sa apariție. Se consideră că elementele aflate în dreapta celui eliminat se deplasează o poziție la stânga (acoperă golul lăsat).

Se dă un șir de matrice pătratice asupra căruia se pot face două tipuri de operații: actualizare a unui element (se înlocuiește matricea de pe acea poziție cu alta) și interogarea unui interval de indici (determinarea produsului matricelor memorate între cei doi indici, inclusiv).

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