# PBinfo #4470 – turnulete – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Un elev dispune de n cuburi, pentru fiecare cub cunoscându-se latura sa c[i]. El dorește să construiască m turnuri, fiecare turn conținând doar cuburi de aceeași dimensiune. Să se determine înălțimea maximă care se poate obține pentru fiecare din cele m turnuri.

Date de intrare
Programul citește de la tastatură numărul n, numărul de cuburi. Pe a doua linie se găsesc n valori naturale în ordine crescătoare, separate prin câte un spațiu, reprezentând dimensiunea cuburilor. Pe următorul rând se găsește valoarea m, reprezentând numărul de turnuri care trebuie construite. Pe următorul rând se găsesc m valori naturale, separate prin câte un spațiu reprezentând dimensiunea cubului folosit la construirea turnului.

Date de ieșire
Programul va afișa pe ecran numărul m numere naturale, separate prin câte un spațiu, înălțimea ma ximă care se poate obține pentru fiecare turn.

Restricții și precizări

1 ≤ n, m ≤ 100.000
cele n numere citite de pe al doilea rând vor fi numere naturale nenule mai mici ca 1.000.000.000
valorile de pe ultimul rând sunt cuprinse între 1 și 1.000.000.000;
dacă nu există niciun cub de dimensiunea cerută, atunci înălțimea turnului care se poate construi este 0;
după construirea unui turn, cuburile se pun la loc și pot fi folosite la construirea altui turn;
pentru teste în valoare de 30 de puncte 1 ≤ n, m ≤ 1000;
pentru alte teste în valoare de 30 de puncte 1 ≤ c[i] ≤ 1.000.000

Exemplu:
Intrare

10
1 3 3 3 5 6 6 8 8 8
4
6 4 5 3
Ieșire

12 0 5 9
Explicație
Se vor construi 4 turnuri.
La construirea primului turn se folosesc cuburi cu latura 6. Înălțimea maximă a turnului este 12.
Al doilea turn trebuie construit cu cuburi de dimensiune 4. Nu există asemenea cuburi, înălțimea turnului va fi 0.
La al treilea turn se folosesc cuburi de latură 5. Există un singur cub cu această dimensiune, deci înălțimea va fi 5.
Ultimul turn va avea înălțimea 9, deoarece conține 3 cuburi de latură 3.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int n, m, a[100002];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; i++){
        int x;
        cin >> x;
        if(x < a[1] or x > a[n]) cout << "0 ";
        else{
            int l = 1, r = n, R = 0, L = 0;
            while(l <= r){
                int mid = l + (r - l) / 2;
                if(a[mid] <= x){
                    R = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            l = 1; r = n;
            while(l <= r){
                int mid = l + (r - l) / 2;
                if(a[mid] >= x){
                    L = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            if(a[L] == x) cout << 1LL * x * (R - L + 1) << " ";
            else cout << "0 ";
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4470)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4470/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4470/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)