Lista de probleme 46

Eroul nostru, Mao, a ajuns în Crângul de Bambuși din Universul Paralel unde înălțimile tulpinilor de bambus sunt amețitoare. În crângul din acest univers se află n tulpini de înălțimi h[1], h[2], …, h[n]. Mao are nevoie să taie cel puțin M metri de bambus, așa că el procedează astfel: își alege o înălțime H și trece pe la fiecare tulpină în parte. Dacă bambusul i are înălțimea h[i] mai mare decât H, atunci taie din el partea de sus astfel încât să rămână exact H metri, iar dacă bambusul are cel mult H metri, atunci nu taie deloc. Să se determine înălțimea maximă H pe care o poate fixa Mao astfel încât după tăiere să poată pleca acasă cu cel puțin M metri de bambus.

Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului y dacă apare în x.

Într-o școală sunt n clase, fiecare având un număr diferit de elevi. Școală primește m pachete cu cărți, fiecare cu un număr diferit de cărți. Pentru ca o clasa să primească un pachet, numărul elevilor din acea clasa trebuie să fie egal cu numărul cărților din pachet. Să se determine câte clase primesc un pachet de cărți.

Un jucător de jocuri video pe calculator vrea să ajungă primul în clasament. El cunoaște punctajele celorlalți jucători și vrea să știe care este poziția sa în clasament după fiecare rundă a jocului.

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y. Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Se dă un șir ordonat crescător a1, a2, …, an de numere întregi. Asupra șirului putem efectua trei tipuri de interogări:

• 1 x – Câte numere din șir sunt mai mici sau egale decât x?
• 2 x – Câte numere din șir sunt mai strict mai mari decât x?
• 3 x – De câte ori apare în șir valoarea x?

Să se răspundă la Q interogări.

Se consideră un șir de numere naturale nenule a[1], a[2], ..., a[n]. Asupra șirului se efectuează Q interogări de forma: care este numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S ?

Cerință

Trebuie să răspundeți la cele Q interogări.

Se consideră un șir de numere naturale nenule a[1], a[2], …, a[n]. Asupra șirului se efectuează Q interogări. Fiecare interogare este dată de o pereche (x, s): care este indicele maxim p cu proprietatea că a[i] ≤ x, pentru orice i=1..p și în plus a[1] + a[2] + ... + a[p] <= s?
Trebuie să răspundeți la fiecare din cele Q întrebări.

Se dau coordonatele a n puncte în plan și razele a m cercuri cu centrul în originea sistemului de coordonate. Scrieți un program care determină numărul de puncte conținut de fiecare cerc.

Se dau n dulapuri, numerotate de la 1 la n, pentru fiecare dulap cunoscându-se numărul de mingi care pot fi plasate în dulap. Se dau m mingi numerotate de la 1 la m. Toate mingile se pun în dulapuri. Pentru fiecare din cele k mingi solicitate să se precizeze în ce dulap au fost repartizate.