| Fişierul intrare/ieşire: | caramizi.in, caramizi.out | Sursă | Stelele Informaticii 2009, clasele 9-10 |
| Autor | Liviu Ciortea | Adăugată de |  Liviu Ciortea •efer |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 36852 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Caramizi
Haralambie s-a decis sa incerce o noua afacere in domeniul constructiilor. A procurat deja N tipuri de caramizi de dimensiuni identice dar de culori diferite, din fiecare tip existand Ci caramizi. El va aseza caramizi unele peste altele pentru a construi turnuri dupa urmatoarele reguli:
- Fiecare turn trebuie sa contina doar caramizi de culori diferite.
- Toate turnurile trebuie sa aiba aceeasi inaltime.
Scopul pe care si-l propune Haralambie este de a folosi cat mai multe caramizi in constructiile sale. Nefiind pasionat de informatica, se bazeaza pe voi sa ii raspundeti la M intrebari de tipul: "Care este numarul maxim de caramizi pe care il pot folosi pentru a construi cel mult Li turnuri?". In afara de glorie, Haralambie va asigura ca o sa va ofere si caramizile ramase.
Date de intrare
Fişierul de intrare caramizi.in va contine pe prima linie numerele N si M cu semnificatiile din enunt. Pe urmatoarea linie se vor afla N numere naturale C1, C2 ... CN, reprezentand numarul de caramizi din fiecare tip. Pe ultima linie se vor afla M numere L1, L2, ..., LM, cu semnificatia din enunt.
Date de ieşire
În fişierul de ieşire caramizi.out se vor afla M linii, fiecare continand raspunsul la intrebarea corespunzatoare din fisierul de intrare.
Restricţii
- 1 ≤ N ≤ 200 000
- 1 ≤ M ≤ 200 000
- 1 ≤ Ci ≤ 1 000 000
- 1 ≤ Li ≤ 2 000 000 000
- Pentru 30% din testele folosite la evaluare 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ Ci ≤ 100, 1 ≤ Li ≤ 100.
- Pentru alte 20% din testele folosite la evaluare 1 ≤ N ≤ 500, 1 ≤ M ≤ 5 000, 1 ≤ Ci ≤ 100, 1 ≤ Li ≤ 5 000.
- Pentru alte 30% din testele folosite la evaluare 1 ≤ Li ≤ 1 000 000.
- Pentru afisarea rezultatelor se recomanda folosirea intregilor cu semn pe 64 de biti.
Exemplu
| caramizi.in | caramizi.out |
|---|---|
| 5 5 4 7 10 11 13 3 12 13 14 21 | 15 40 40 42 45 |
Explicaţie
In primul caz, Haralambie construieste 3 turnuri, fiecare continand toate cele 5 tipuri de caramizi, aranjate oricum. Urmatoarele doua cazuri au aceeasi solutie, in care Haralambie construieste 10 turnuri de cate 4 caramizi fiecare. In al patrulea caz, Haralambie va folosi un numar maxim de caramizi construind 14 turnuri de cate 3 caramizi fiecare. In ultimul caz, Haralambie poate folosi toate caramizile pe care le are la dispozitie.
