Lista de probleme 8

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3201 IJK

Se dă un şir a cu n numere naturale. Aflaţi numărul tripletelor (i,j,k), cu 1 ≤ i < j < k ≤ n, pentru care avem a[i] > a[j] < a[k].

#1794 aint

Se dă un vector cu N elemente numere naturale numerotate de la 1 la N și M operații de forma:

  • 1 x y, cu semnificația: elementul de poziția x ia valoarea valoarea y.
  • 2 x y: se determină valoarea minimă a elementelor cu indici cuprinși între x și y.

Afișați rezultatele operațiilor de tipul 2.

#1870 easyxy

Se dă un vector v cu N elemente numere naturale numerotate de la 1 la N și M întrebări de forma:

  • x y p: se afișează valoarea ce s-ar afla pe poziția p dacă v[x...y] ar fi ordonat crescător.

Se dă un arbore cu n noduri şi rădăcina r, nodurile fiind etichetate cu numerele de la 1 la n. Se cere să se afle pentru fiecare nod i, câte noduri din subarborele cu rădăcina i au eticheta mai mică decât i.

#1692 Calafat

Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între 2 indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st,dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.

#1816 Unicorn

Este ziua unicornului Corn şi prietenii lui vor să-i pregătească o surpriză, un mare turn de clătite! Totul trebuie să fie perfect, și toată lumea știe că cel mai frumos turn are formă de corn (clătitele sunt așezate în ordine strict descrescătoare după rază). Ei pregătesc clătite de diferite mărimi și le așază una peste alta. Fiecare clătită are o anumită valoare nutritivă. După ce termină de gătit, aceștia vor să creeze un turn de clătite in formă de corn pentru prietenul lor Corn. Astfel, unicornii pot alege să mânance oricâte clătite vor, clătitele rămase păstrându-și ordinea inițială. Clătitele care rămân în farfurie (pastrând ordinea inițială) trebuie să aibă formă de corn (strict descrescător după rază). Deoarece Corn adoră clătitele, ei vor ca turnul Corn format din clătitele rămase după ce aceștia mănâncă să aibă cea mai mare valoare nutritivă (suma valorilor nutritive ale clătitelor rămase).

Se dă un şir de N numere întregi. Definim costul intervalului [x, y], unde x si y apartin {1, 2, …, N}, ca fiind suma diferenţelor dintre numărul maxim din șir, aflat în interval şi restul numerelor aflate pe pozițiile x, x+1, …, y.

De exemplu, pentru şirul 2 4 7 4 3 -1 2 4 6 costul intervalului [3, 6] este 15. (explicație: 7-7+ 7-4 + 7-3 + 7+1 = 15).

Se definesc M operaţii de forma tip x y, astfel: Dacă tip este 1, atunci elementul de pe poziţia x din șir devine y. Dacă tip este 2, atunci să se afişeze costul intervalului [x, y].

Să se determine răspunsul pentru fiecare operaţie de tipul 2.

Se dă un șir v format din N elemente naturale nenule nu neapărat distincte. Asupra șirului putem aplica un singur tip de operație: interschimbarea a două elemente aflate pe poziții consecutive. Dându-se un număr natural K, se cere șirul minim lexicografic ce se poate obține prin aplicarea a cel mult K interschimbări de elemente de pe poziții consecutive.