Lista de probleme 9

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3085 fsecv

Se consideră un șir A format din N numere întregi, numerotate de la 1 la N. Numim secvență a șirului A orice succesiune de elemente consecutive din șir de forma A[i], A[i+1], …, A[j], cu 0 < i < j ≤ N. Fiind dat șirul A cu N numere întregi se cere să se răspundă la Q întrebări de forma: i j k (0 < i < j ≤ N). Pentru fiecare întrebare se cere să se determine câte numere din secvența A[i], …, A[j] au frecvența de apariții egală cu k.

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

#3759 Cartita

În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de h[i] centimetri. Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță.

#2725 aib

Aveți la dispoziție un număr natural nenul n și o permutare a = (a[1], a[2], ..., a[n]) a mulțimii {1, 2, ..., n}. Pentru fiecare număr a[i] trebuie să determinați câte numere mai mici decât a[i] se află la stânga sa, adică în secvența a[1], a[2], ..., a[i-1].

Se dau un șir de N numere naturale nenule indexat de la 1 și Q query-uri de forma l r. Să se afișeze pentru fiecare query l r medianul secvenței l r din șir.

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

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Se dă o listă, inițial vidă, cu numere. Toor dorește să completeze lista asta, adăugând numere pe care le consideră importante pentru cmmdc. La fiecare moment, dorește să afle cmmdc-ul tuturor numerelor care sunt în listă atunci. Câteodată, scoate un număr care este în listă, pentru a putea adăuga ulterior altele. Prin convenție, cmmdc-ul unei mulțimi cu 0 elemente este 1. Să se determine după fiecare operație cmmdc-ul mulțimii actuale de numere.