Lista de probleme 101

Suntem în anul 2050. Resursele de apă de pe planeta noastră sunt limitate din cauza schimbărilor climatice. Sistemul de stocare a apei al unui oraș a evoluat în timp, ajungându-se la o configurație flexibilă formată din n pereţi verticali paraleli \( {p}_{1}, {p}_{2}, \cdots {p}_{n} \). Fiecare perete \( {p}_{i} \) are forma unui dreptunghi cu înălțimea \( {a}_{i} \) şi lăţimea de 1 km, iar oricare doi pereţi alăturaţi \( {p}_{i}, {p}_{i+1} \) se află la distanţa de 1 km, faţă în faţă. Fiecare dintre acești pereți poate fi coborât complet, prin culisare pe verticală, iar un bazin poate fi format din oricare doi pereți \( {p}_{i}, {p}_{j} \) (rămaşi după coborârea tuturor celorlalți) şi din pereţi laterali, care întregesc conturul de bazin. Capacitatea unui bazin este dată de produsul dintre înălţimea peretelui celui mai mic dintre cei doi \( {p}_{i}, {p}_{j} \) din care este format bazinul şi distanța dintre aceşti doi pereți. Sistemul de stocare poate fi descris de un șir de numere naturale \( {a}_{1}, {a}_{2}, …..{a}_{n} \)strict pozitive, unde \({a}_{1} \)reprezintă înălțimea în kilometri a peretelui \({p}_{1} \), \({a}_{2} \) reprezintă înălțimea în kilometri a peretelui \({p}_{2} \) și așa mai departe.

Scrieți un program care primește la intrare numărul de pereți n≥2 și înălțimile acestora \( {a}_{1}, {a}_{2}, \cdots {a}_{n} \) , iar apoi determină și scrie capacitatea maximă de apă care poate fi stocată în acel oraș.

Se dă un vector cu n elemente, numere naturale. Verificați dacă vectorul are un element majoritar. Numim element majoritar o valoare pentru care numărul de apariții în vector este mai mare decât n/2.

Se dau două şiruri cu elemente numere naturale. Determinaţi câte dintre elementele primului şir sunt mai mari decât toate elementele celui de-al doilea şir.

Alexandru este foarte pasionat de cuburi. Într-o zi, acesta a creat un zid format din N turnuri de cuburi, turnul i fiind alcătuit din H[i] cuburi puse unul peste altul. Având acest zid, el își pune următoarea întrebare: Dacă aș porni de la un zid “gol” cu N turnuri (gol înseamnă ca H[i] = 0 pentru orice 1 ≤ i ≤ N) iar singura operație pe care o pot face este să aleg doi indici i și j cu 1 ≤ i ≤ j ≤ N și să pun câte un cub peste fiecare turn în intervalul i și j, care este numărul minim de astfel de operații ce trebuie efectuate pentru a obține zidul inițial?

Se consideră un șir a[1], a[2], …, a[n] de numere întregi. Să se determine diferența maximă de forma a[i] - a[j], unde 1 ≤ i < j ≤ n.

Se dă un șir de \(n\) numere naturale \(a_1,a_2,\dots,a_n\). Asupra șirului se aplică următoarele operații în această ordine:

• Se inversează prefixul \(a_1,a_2,\dots,a_{n-2},a_{n-1},a_n\);
• Se inversează prefixul \(a_1,a_2,\dots,a_{n-2},a_{n-1}\);
• Se inversează prefixul \(a_1,a_2,\dots,a_{n-2}\);
• …
• Se inversează prefixul \(a_1,a_2\).

Să se determine șirul după finalizarea operațiilor.

Pe o platformă sunt montate pe poziții consecutive n bare verticale de lățime 1cm. Vom presupune că platforma este mărginită față/spate de ziduri transparente de înălțime infinită. Cantitatea de apă ce poate fi reținută într-o unitate de volum (1cm x 1cm x 1cm) este de 1 litru. Determinați cantitatea de apă reținută.

Dându-se un șir cu n elemente numere naturale, să se construiască pentru fiecare element din șir câte un tabel al claselor de resturi asociat prin înmulțire dacă indicelele elementului este impar, respectiv prin adunare dacă indicele elementului este par.

Se consideră N copii, numerotați de la 1 la N și fiecare face parte dintr-o clasă. Inițial sunt n clase și fiecare copil face parte din propria sa clasă. Se dau M operații de două tipuri:

• 1 x y – acțiune: clasele din care fac parte copiii cu numerele x și y se reunesc. Dacă x și y fac deja parte din aceeași clasă, operația nu se efectuează
• 2 x y – întrebare: copiii cu numerele x și y sunt sau nu în aceeași clasă?

Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.

Se cere determinarea maximului şi minimului valorilor dintr-un sir