== include(page="template/taskheader" task_id="bile2") ==
Poveste si cerinta...
Miruna tocmai a invatat la ora de matematica despre probabilitati. Ea stie ca probabilitatea ca un eveniment sa se intample poate fi exprimata sub forma unui raport subunitar care este egal cu numarul de cazuri favorabile impartit la numarul de cazuri totale. De exemplu, daca cineva trebuie sa spuna o cifra la intamplare, probabilitatea ca acea cifra sa fie mai mica decat $3$ este de $3/10$. Cazurile favorabile sunt cele in care va spune $0$, $1$ sau $2$, iar numarul total de cazuri este egal cu $10$, reprezentand numarul total de cifre. Dupa ora de matematica unde a invatat despre probabilitati, Miruna a ajuns acasa si a inceput sa se joace cu bilele fratiorului ei. Ea are la dispozitie $N$ bile numerotate de la $1$ la $N$, pe care le arunca intr-o urna. Miruna se gandeste apoi la $3$ numere intregi $D$, $A$ si $B$. Dupa ce a ales aceste numere, fetita din poveste se intreaba care ar fi numarul minim de bile pe care ar trebui sa le scoata din urna, astfel incat probabilitatea sa existe cel putin doua bile extrase cu diferenta in modul a numerelor inscrise pe ele mai mica sau egala cu $D$, sa fie mai mare sau egala cu raportul $A/B$.
h2. Date de intrare
Fisierul de intrare $bile2.in$ ...
Fisierul de intrare $bile2.in$ va contine pe prima linie $2$ numere intregi, $N$ si $D$. Pe a doua linie se va gasi numarul $A$, iar pe a treia numarul $B$. Aceste valori au semnificatia din enunt.
h2. Date de iesire
In fisierul de iesire $bile2.out$ ...
Fisierul de iesire $bile2.out$ va contine un singur numar intreg, reprezentand numarul minim de bile ce trebuie extrase.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1000$
* $1 ≤ D < N$
* {$1 ≤ A ≤ B ≤ 10^64^$}
* {$Pentru 30% din teste N ≤ 20, iar A, B ≤ 10^2^$}
* {$Pentru inca 30% din teste N ≤ 50, iar A, B ≤ 10^4^$}
h2. Exemplu
table(example). |_. bile2.in |_. bile2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 1
4
6
| 3
|
h3. Explicatie
...
* Daca Miruna ar fi extras o singura bila, atunci probabilitatea ar fi fost egala cu $0$.
* Daca Miruna ar fi extras $2$ bile, am fi avut urmatoarele posibilitati:
$*1* *2*$
$1 3$
$1 4$
$*2* *3*$
$2 4$
$*3* *4*$
Numarul de cazuri favorabile este egal cu $3$, iar numarul de cazuri totale cu $6$. Dar $3/6 < 4/6$.
* Daca Miruna extrage $3$ bile, avem cazurile:
$*1* *2* *3*$
$*1* *2* 4$
$1 *3* *4*$
$*2* *3* *4*$
Observam ca numarul de cazuri favorabile este egal cu numarul de cazuri totale. $4/4 > 4/6$, deci $3$ este raspunsul cautat.
== include(page="template/taskfooter" task_id="bile2") ==
