Lista de probleme 18

Filtrare

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

#4198 wall1

Cetatea Sucevei, construită de Petru Mușat în timpul zilelor glorioase ale Moldovei medievale de la sfârșitul secolului 14, și consolidată în al 15-lea secol de către Ștefan cel Mare, este cunoscută pentru faptul că nu a fost niciodată capturată de Imperiul Otoman. Sistemul medieval de fortificații al cetății a fost compus din diferite construcții (curți regale, mănăstiri cu pereți înalți și puncte strategice semnificative) concepute în scopuri defensive, care au fost înconjurate de ziduri înalte de piatră. Dată fiind configurația zidului înainte de restaurare, compusă din N turnuri, indexate de la stânga la dreapta folosind numerele naturale cuprinse între 1 și N, și pentru fiecare turn având numărul de blocuri de piatră pe care îl conține, găsiți lungimea maximă a fragmentului de zid care poate fi restaurat, astfel încât restauratorii să folosească toate cele S blocuri de piatră recuperate în fragment. Lungimea fragmentului este definită ca numărul de turnuri conținute în acesta.

Se consideră o matrice cu n linii şi n coloane şi elemente egale cu 0 sau 1. Să se calculeze determinantul matricei.

În planul xOy se găsesc n puncte de coordonate numere naturale, nu neapărat aflate pe poziții distincte. Pentru fiecare punct din plan de coordonate (x, y) trebuie să spuneți câte alte puncte au coordonatele (p, q) cu proprietatea că 0 ≤ p < x și 0 ≤ q ≤ y (atenție, p este strict mai mic decât x, iar q este mai mic sau egal cu y).

Josephus este un matematician înrăit.
Într-o zi acesta se joacă cu primele N numere prime, când se decide să își construiască propiul său șir circular format din aceste numere. Pe prima poziție se va afla primul număr prim, adică 2, iar mai apoi se parcurge circular șirul din K în K, completându-se cu restul de numere prime, până la repartizarea tuturor.

Se dă un vector de N numere naturale nenule, indexat de la 1.
Se cere să se raspundă la Q interogări de tipul:

  • pentru un interval [l, r] din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.

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