Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-02-25 17:33:47.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:swaps.in, swaps.outSursăAlgoritmiada 2012, Runda 3
AutorPaul-Dan BaltescuAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 fi 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-9
  • 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.inswaps.out
3
6 3 1 4
6 4 1 1
3 3 2 3
0.117283951
0.331275720
0.320987654
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?