Kártyatrükk

Bűvésztrükköket tanulok, hogy lenyűgözzem a barátnőmet, Alice-t. Az utolsó trükköm egy valószínűségi trükk, ami azt jelenti, hogy legtöbbször működik, de nem minden esetben. A trükk végrehajtásához először is összekeverek sok kártyát, és lerakom őket az asztalra egy sorban, színükkel felfelé. Ezután Alice kiválaszt egyet az első tíz kártya közül titokban (azaz választ egy x₀-t, egy titkos számot 1 és 10 között), majd ismételve kihagy néhány kártyát a következők szerint: miután kiválasztott egy kártyát az x_i pozícióban, c(x_i) számmal a színén, következőnek az x_i+1 = x_i + c(x_i) pozícióban lévő kártyát fogja kiválasztani. A bubi (J), a dáma (Q) és a király (K) 10-et, az ász (A) 11-et ér. Feltételezheted, hogy legalább tíz kártya van az asztalon.

Alice akkor fejezi be ezt a folyamatot, amikor már nincs kártya az x_i + c(x_i) pozícióban. Ezután én is végrehajtom ugyanezt az eljárást egy véletlenszerűen kiválasztott kezdőpozícióból, amely különbözhet az Alice által választottól. Az derül ki, hogy gyakran ugyanabban a pozícióban végzünk. Alice teljesen le van nyűgözve ettől a trükktől.

Engem azonban jobban érdekel a trükk hátterében lévő matematika. Ha adott a véletlenszerűen kiválasztott kezdőpozícióm, valamint az összes kiválasztott kártya értéke (beleértve az utolsót is), ki tudnád számítani annak a valószínűségét, hogy Alice olyan kezdőpozíciót választott, amellyel ugyanazon a kártyán fejezzük be a játékot? Feltételezheted, hogy a kezdőpozícióját véletlenszerűen választja ki egyenlő valószínűséggel (1 és 10 között). Elfelejtettem feljegyezni az általam kihagyott kártyákat, ezeket tehát nem ismerjük. Azt is feltételezheted, hogy az ismeretlen kártyák értéke független a többi kártya értékétől, és hogy véletlenszerű értékek azonos valószínűséggel a lehetséges értékek (azaz 2–10, J, Q, K és A) közül.

1. ábra: Az első példa bemenet illusztrációja. A kezdőpozícióm 2, tehát azt a kártyát választom először. Ezután újra és újra kihagyok kártyákat a kiválasztott kártya értékétől függően. Ez a folyamat addig ismétlődik, amíg nem marad elég kihagyandó kártya (ebben a példában a Q-ig). Az utolsó Q kártyát 0–9 darab ismeretlen kártya követi, mivel a Q 10-et ér.

A bemenet specifikációja

Minden teszteset két sorból áll:

• Az első sor két egész számot tartalmaz, n-et és m-et (1 ≤ n ≤ 100, 1 ≤ m ≤ 10), ahol n a kiválasztott kártyák számát, m pedig az elsőnek kiválasztott kártya pozícióját adja meg (az asztalon lévő első kártya sorszáma 1).
• A második sorban n szimbólum szerepel, amelyek az n darab kiválasztott kártya értékét adják meg (sorrendben, az utolsó kártyát is beleértve). Minden érték vagy egy x egész szám (2 ≤ x ≤ 10), vagy egy karakter (J, Q, K vagy A, a fent leírtaknak megfelelően).

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni annak a valószínűségével, hogy Alice olyan kezdőpozíciót választ, amely ugyanahhoz az utolsó kártyához vezet, mint a tesztesetben megadott utolsó kártya. Az eredmény abszolút hibája legfeljebb 10^–7 lehet.

Példa bemenet

1. 5 2
2. 2 3 5 3 Q
3. 1 1
4. A
5. 1 2
6. A
7. 1 10
8. A
9. 6 1
10. 2 2 2 2 2 2
11. 7 1
12. 2 2 2 2 2 2 2
13. 3 10
14. 10 J K

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 0.4871377757023325348071573
2. 0.1000000000000000000000000
3. 0.1000000000000000000000000
4. 0.1748923357025314239697490
5. 0.5830713210321767445117468
6. 0.6279229611115749556280350
7. 0.3346565827603272001891974

letöltés szöveges állományként