Fişierul intrare/ieşire:caramizi.in, caramizi.outSursăStelele Informaticii 2009, clasele 9-10
AutorLiviu CiorteaAdăugată deeferLiviu Ciortea efer
Timp execuţie pe test0.175 secLimită de memorie36852 kbytes
Scorul tăuN/ADificultateN/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:

  1. Fiecare turn trebuie sa contina doar caramizi de culori diferite.
  2. 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.incaramizi.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content