Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | minim2.in, minim2.out | Sursă | Stelele Informaticii 2010 |
| Autor | Drutu Bogdan | Adăugată de |  dragus marius •mariusdrg |
| Timp execuţie pe test | 0.55 sec | Limită de memorie | 12096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Minim2
Lavinia tocmai s-a apucat de ciclism si vrea neaparat sa intre in cartea recordurilor asa ca si-a ales un traseu format din N portiuni pe care vrea sa bata recordul. Din pacate ea nu este suficient de bine pregatita asa ca apeleaza la ajutorul vostru. Voi aveti posibilatea de a inmulti lungimea oricarei portiuni o data cu un numar subunitar A si de oricate ori dupa cu un alt numar subunitar B, A ≤ B. Care este numarul minim de actionari care trebuie sa le faceti astfel incat Lavinia sa bata recordul.
Date de intrare
Pe prima linie a fisierului de intrare minim2.in se va gasi un numar intreg N, reprezentand numarul de portiuni. Pe urmatorul rand se vor gasi N numere naturale reprezentand lungimile portiunilor. Pe al 3-lea rand se vor afla 3 numere reale, A, B si recordul de batut.
Date de ieşire
Pe prima linie a fisierului de ieşire minim2.out se va gasi numarul minim de actionari care trebuiesc efectuate astfel incat Lavinia sa bata recordul.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ D[i] ≤ 1.000.000.000
- 0 ≤ A ≤ B ≤ 1
- Pentru 40% din teste nu vor fi efectuate mai mult de 200.000 de actionari.
Exemplu
| minim2.in | minim2.out |
|---|---|
| 4 5 10 100 18 0.5 0.75 52.4 | 4 |
Explicaţie
Prima data se actioneaza asupra traseului 3, 100 * 0.5 = 50. A 2-a oara se actioneaza din nou asupra sectorului 3 50*0.75=37.5, suma fiind 70.5. A 3-a oara se actioneaza tot asupra sectorului 3, 37.5*0.75=28.125. A 4-a oara se actioneaza asupra sectorului 4 18*0.5=9. Si astfel suma este 5+10+28.125+9=52.125.
