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
Domnul B. este un artist modern. Ultima sa mare creatie este, intr-o forma extrem de stilizata, permutarea identica de lungime N (adica permutarea 1, 2, 3 ... N).
Domnul C. este malitios. Ultimul sau mare plan este de a distruge ultima mare creatie a Domnului B., facand interschimbari aleatoare ale unor numere din permutare. Mai exact, la un pas, Domnul C. isi va alege cu probabilitate egala doua pozitii, i si j si va interschimba continutul celor doua pozitii din permutare.
Domnul C. are in cap T intrebari, iar in functie de raspunsurile voastre isi va alege cea mai malitioasa strategie pentru a distruge creatia Domnului B. O intrebare are forma urmatoare: N P A B, cu semnificatia "Care este probabilitatea ca dupa P pasi, numarul A sa ajunga pe pozitia B intr-o permutare de lungime N?"
Ajutati-l pe Domnul C., raspunzand corect la fiecare dintre cele T intrebari.
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 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 ≤ 10.000
- 1 ≤ A, B ≤ N
- 1 ≤ P ≤ 1.000.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, N ≤ 100 si P ≤ 100.
- Pentru alte 20% din teste, P ≤ 100.000.
Exemplu
| swaps.in | swaps.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
