Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | swaps.in, swaps.out | Sursă | Algoritmiada 2012, Runda 3 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Swaps
Definim functia f(N, P, A, B) ca fiind probabilitatea ca numarul A sa ajunga pe pozitia B dupa efectuarea a P interschimbari aleatoare de cate doua numere asupra permutarii identice de lungime N. De exemplu, f(3, 1, 1, 2) este egal cu 0.(2), deoarece avem 9 posibilitati de alegere a pozitiilor interschimbate, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), dintre care doar doua produc rezultatul dorit $((1, 2) si (2, 1)).
Dandu-se T teste de forma N P A B, sa se calculeze pentru fiecare dintre acestea f(N, P, A, B).
Date de intrare
Fişierul de intrare swaps.in va contine pe prima linie numerele naturale N si T. Urmatoarele T linii vor contine triplete de forma N P A B, cu semnificatia din enunt.
Date de ieşire
În fişierul de ieşire swaps.out se vor afla raspunsurile la cele T intrebari, pe linii diferite.
Restricţii
- 1 ≤ N ≤ 1.000.000
- 1 ≤ A, B ≤ N
- 1 ≤ P ≤ 1.000.000
- 1 ≤ T ≤ 100.000
- Rezultatele se vor afisa cu o precizie de 10-6
- A si B pot sa fie si egale.
- In cazul in care pozitiile alese pentru interschimbare sunt identice, permutarea va ramane la fel pentru pasul urmator.
- Pentru 20% din teste, T ≤ 20, N ≤ 100 si P ≤ 100.
- Pentru alte 20% din teste, T ≤ 20 si P ≤ 100.000.
Exemplu
| swaps.in | swaps.out |
|---|---|
| 3 6 3 1 4 6 4 1 1 3 3 2 3 | 0.117283951 0.331275720 0.320987654 |
