| 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
Printr-un portal magic, un număr mare de gândaci au ieşit din Bugland şi au invadat o cramă.
Se ştie despre cramă că are N camere, fiecare cameră fiind plină de butoaie de vin, iar în a i-a cameră se află Vi gândaci. Deţinătorii cramei au la dispoiziţie două tipuri de insecticide: K spray-uri numite AntiBug , care elimină dintr-o cameră P gândaci pe zi, şi N-K spray-uri numite ZeroBugs , care elimină dintr-o cameră Q gândaci pe zi.
Zilnic, în fiecare cameră se dă cu spray pentru a scăpa de gândaci.
Având la dispoziţie resursele date, care este numărul minim de zile în care pot fi salvate butoaiele de vin prin eliminarea tuturor gândacilor?
Date de intrare
Din butoaie.in se vor citi 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 numărul de Vi gândaci din camera i.
Date de ieşire
În butoaie.out se va afişa, pe prima şi singura linie, numărul minim de zile necesare pentru elimina toţi gândacii.
Restricţii
- Pentru teste in valoare de 40 de puncte
- Într-o cameră se poate da cu un singur tip de spray într-o anumită zi, două spray-uri diferite nu pot fi folosite împreună pentru că ar avea un efect toxic asupra butoaielor de vin, iar două spray-uri de acelaşi fel nu au rost să fie folosite împreună deoarece efectul lor nu creşte.
Exemplu
| butoaie.in | butoaie.out |
|---|---|
| 5 2 3 1 5 3 4 8 7 | 4 |
Explicaţie
După prima zi: 3 4 5 7 8 -> 2 3 4 4 5 (din camerele 4 şi 5 se elimină câte 3 gândaci, iar din camerele 1, 2 şi 3, câte 1 gândac)
După a doua zi: 2 3 4 4 5 -> 1 2 3 1 2 (din camerele 4 şi 5 se elimină câte 3 gândaci, iar din camerele 1, 2 şi 3, câte 1 gândac)
După a treia zi: 1 2 3 1 2 -> 0 1 0 0 0 (din camera 3 se elimină 3 gândaci, din camera 5 se elimină 2 gândaci, iar din camerele 1, 2 şi 4, câte 1 gândac)
După a patra zi: 0 1 0 0 0 -> 0 0 0 0 0 (din camera 2 se elimină 1 gândac)
