Lista de probleme 11

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.

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.

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

#3510 AIB2D

Se dă o matrice pătratică de dimensiune N. Asupra ei se fac 2 tipuri de operații:

  • 1 x y val – elementul de coordonate x y crește cu val
  • 2 x1 y1 x2 y2 – se cere suma elementelor submatricei cu colțul stânga-sus de coordonate x1 y1 și cel drepta jos de coordonate x2 y2.

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

#2012 TSM

TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține 4 jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei 4 prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă de joc acțiunile se petrec pe un câmp de luptă, inițial gol, iar apărătorii disting următoarele evenimente:

1 x : TH observă că Mygo a trimis pe câmpul de luptă un tanc de coeficient x și își anunță aliații.
2 K : Seba consideră că cel mai periculos tip de tanc aflat pe câmpul de luptă este cel cu al K – lea cel mai mic coeficient și îl afișează în consolă, pe un nou rând.
3 : Năstuț scrie în consolă, pe un nou rând, coeficientul cel mai mic al unui tanc aflat în momentul respectiv pe câmpul de luptă.
4 : Șcuțu trage cu tunul într-un tanc de coeficient egal cu ultimul scris de Seba în consolă și îl elimină.

#2779 cntSQ

Se dă o matrice binară (valori 0 și 1). Să se determine câte pătrate exista cu proprietatea că acestea au pe marginea lor doar valori 1.

Aflați numărul subsirurilor strict crescătoare de lungime k.

Se consideră un şir format din n numere naturale şi un număr dat k. Să se determine numărul secvenţelor din şir care au proprietatea că suma elementelor secvenţei este de cel puţin de k ori mai mare sau egală decât numărul elementelor secvenţei.

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