Fişierul intrare/ieşire:bile2.in, bile2.outSursăStelele Informaticii 2007, clasele 9-10
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bile2

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.

Date de intrare

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.

Date de iesire

Fisierul de iesire bile2.out va contine un singur numar intreg, reprezentand numarul minim de bile ce trebuie extrase.

Restrictii

  • 1 ≤ N ≤ 1000
  • 1 ≤ D < N
  • 1 ≤ A ≤ B ≤ 1064
  • Pentru 30% din teste N ≤ 20, iar A, B ≤ 102
  • Pentru inca 30% din teste N ≤ 50, iar A, B ≤ 104

Exemplu

bile2.inbile2.out
4 1
4
6
3

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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content