Lista de probleme 8

Filtrare

Dificultate

Operații intrare/ieșire

#2534 Bogdan

Bogdan și Ionuț au fost prieteni încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a
rezolva problema împreuna.

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 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 dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact un interval din descompunere). De exemplu, pentru perechea 5,10, o descompunere în intervale este [5,5], [6,8],[9,10].
Dorim să realizăm o descompunere în intervale a tuturor celor M perechi de numere date, astfel încât să se îndeplinească condițiile următoare (notăm L = 1 + [log2N]).

  • fiecare pereche să aibă în descompunere maxim 2*L intervale.
  • numărul total de intervale distincte cu mai mult de un element care apar în descompuneri să nu depășească valoarea N.

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

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