Se considera un vector v cu n elemente distincte, indexate de la 0 la n-1. Se aplica urmatorul algoritm de amestecare: pentru i de la 0 la n-1: swap(v[i], v[random(n)]) unde swap(a,b) interschimba valorile elementelor a si b, iar random(n) returneaza, cu probabilitate uniforma 1/n, un numar aleator intre 0 si n-1 inclusiv. Stiind ca elementul urmarit se afla initial pe pozitia p0, care este probabilitatea ca, dupa executarea algoritmului, elementul urmarit sa se afle pe pozitia p (calculata ca o fractie exacta, redusa la forma ireductibila)?
- Date de intrare
- Se citesc pe o singura linie, separate prin spatiu, trei numere naturale n, p0 si p, reprezentand numarul de elemente ale vectorului, pozitia initiala a elementului urmarit, respectiv pozitia finala pentru care se cere probabilitatea.
- Date de iesire
- Se afiseaza pe ecran probabilitatea ceruta, ca fractie ireductibila in formatul 'numarator/numitor'.
- Restrictii
- 2 <= n <= 6, 0 <= p0 <= n-1, 0 <= p <= n-1
Exemple
Exemplul 1
Intrare
3 2 0
Iesire
8/27
Exemplul 2
Intrare
2 0 1
Iesire
1/2