Programozó versenyek

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2014. november 30.

2014. november 30. 10:30 – 2014. november 30. 15:30

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 x0-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 xi pozícióban, c(xi) számmal a színén, következőnek az xi+1 = xi + c(xi) 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 xi + c(xi) 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 210, 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
Debreceni Egyetem, Informatikai Kar, v. 2024.09.30.