Lista de probleme 18

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3468 weekend

În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe. Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața sa. Fiind dat șirul inițial de observații ale oamenilor care stau la coadă, să se reconstruiască șirul minim lexicografic care poate reprezenta înălțimile acestora.

Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y].

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 a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații:

  • 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val;
  • 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori);
  • 3 st dr – se cere să se afișeze lungimea cele mai lungi secvențe de numere prime alcătuită exclusiv din elemente ale șirului care au indicii aflați în intervalul [st, dr](o secvență a unui șir este alcătuită din elemente aflate poziții consecutive).

Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.

#2534 Bogdan

Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val.
2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată crescător.

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

#2226 Chimic

Cercetătorii bistrițeni vor să creeze cea mai puternica soluţie stabilă, în limita elementelor disponibile. Ei deţin N elemente chimice reprezentate de numerele 1,2,3...N, cu puteri cunoscute. Puterea unei soluții este dată de suma puterilor elementelor. Nu pot să amestece orice elemente, pentru că soluţia ar deveni instabilă. Ei pot să combine elementele după anumite reguli:

1) Primul element al soluţiei poate fi oricare.
2) Dacă ultimul element al soluţiei curente este i, atunci următorul element trebuie să aparţină intervalului [si,di], pentru că altfel soluţia ar deveni instabilă.

Tu fiind noul angajat trebuie să găseşti puterea cea mai mare unei soluţii.