Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | butoaie.in, butoaie.out | Sursă | IIOT 2019-20 Runda 1 |
| Autor | Pop Ioan Cristian | Adăugată de |  Comisia IIOT 2019-20 •unibucPoli2019 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 64536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Butoaie
O cramă trebuie să transporte vinul produs în urma recoltei din acest an către un centru de depozitare. În cramă se află N butoaie, al i-lea butoi având Li litri de vin. Zilnic, vin N maşini care transportă o parte din vin. K dintre aceste maşini au o capacitate de P litri, iar restul de N-K au o capacitate de Q litri.
Fiecare maşină poate transporta vinul dintr-un singur butoi (nu neaparat acelaşi butoi în fiecare zi), iar două maşini nu pot transporta vin din acelaşi butoi în aceeaşi zi. Astfel, dintr-un butoi pot fi transportaţi fie maxim P litri, fie maxim Q litri, în funcţie de maşina aleasă.
Cerinta
Pentru a economisi cât mai mulţi bani pentru transport, deţinătorii cramei vor să ştie care este numărul minim de zile necesare pentru a transporta tot vinul.
Date de intrare
În fişierul de intrare butoaie.in se vor afla pe prima linie N şi K, pe a doua linie se vor afla P şi Q, iar pe a treia linie se vor afla N numere, al i-lea reprezentând cantitatea de Li litri din butoiul i.
Date de ieşire
În fişierul de ieşire butoaie.out se va afişa, pe prima şi singura linie, numarul minim de zile necesare pentru a transporta tot vinul.
Restricţii
- K ≤ N ≤ 2*105
- P, Q ≤ 109
- Li ≤ 109 pentru 1 ≤ i ≤ N
- Pentru teste in valoare de 40 de puncte K ≤ N ≤ 104, P, Q ≤ 102 şi Li ≤ 104
Exemplu
| butoaie.in | butoaie.out |
|---|---|
| 5 2 3 1 5 3 4 8 7 | 4 |
Explicaţie
O modalitate de a transporta tot vinul în 4 zile este:
După prima zi: 3 4 5 7 8 -> 2 3 4 4 5 (din butoaiele 4 si 5 se transportă câte 3 litrii, iar din butoaiele 1 2 si 3, câte 1 litru)
După a doua zi: 2 3 4 4 5 -> 1 2 3 1 2 (din butoaiele 4 si 5 se transportă câte 3 litrii, iar din butoaiele 1 2 si 3, câte 1 litru)
După a treia zi: 1 2 3 1 2 -> 0 1 0 0 0 (din butoaiul 3 se transportă 3 litrii, din butoiul 5 se transportă 2 litrii, iar din butoaiele 1 2 si 4, câte 1 litru)
După a parta zi: 0 1 0 0 0 -> 0 0 0 0 0 (din butoiul 2 se transportă 1 litru)
