TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

53.8% (7/13)

Submission's AC Ratio

14.7% (11/75)

Description

有沒有聽過一歀名為三國殺的桌上遊戲?

三國殺是主要流行於中國大陸、台灣與港澳的桌上紙牌遊戲。該紙牌遊戲以殺人紙牌(Bang!)為原型,以中國的三國時代及演義文學為背景,擁有不同類型的身份牌、武將牌、體力牌、遊戲牌(包括基本牌、錦囊牌、裝備牌)等。遊戲玩家數量為2-10人。三國殺遊戲由游卡桌遊(Yoka Games)開發,於2008年9月18日在北京、上海和廈門三個城市同步面市。三國殺遊戲的核心為三國殺標準版,可以配合各種擴展包以增加遊戲性。 --維基百科

在三國殺裡,有一張牌叫作「閃電」。這張牌的效果是,持有者需要進行一次判定,如果判定成功則受到三點傷害並將閃電放回棄牌堆,如果判定失敗則將閃電交給下一位玩家。這張牌的殺傷力之大可想而知(一個人最多五滴血)。

為了追求刺激感,有$N$個人圍在一起準備進行「閃電大賽」。閃電大賽即為將閃電的殺傷力發揮到淋漓盡致的一種賽制。一開始$N$個人圍成一圈,順時針依序編號為$1$到$N$。閃電一開始由編號一的玩家持有。之後閃電的持有者都需要進行一次判定,如果判定成功則直接退出遊戲,如果判定失敗則繼續留在場上。不論如何,判定結束之後都將閃電交給順時針方向的下一位存活玩家。最後一位存活於場上的玩家即獲勝。

假設閃電每次判定成功和判定失敗的機率各為一半,請問編號$M$的人獲勝的機率為何?

Input Format

每一組測資僅含一行,包含兩個正整數$1\leq N\leq 10^ 5,1\leq M\leq N$,代表有$N$個人參與遊戲並要詢問第$M$個人獲勝的機率。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 3$ 12
2 (5~9) $N\leq 300$ 22
3 (10~14) $N\leq 5000$ 33
4 (15~19) 無限制 33

Output Format

請輸出一個和答案絕對誤差小於$10^ {-9}$的浮點數,代表編號$M$的人獲勝的機率。

Sample Input

2 1

Sample Output

0.333333333

Hints

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第四次模擬賽pE
題目取自2015 TOI第一階段選訓第二次模擬考pC

Subtasks

For Testdata: 0 ~ 4, Score: 12
For Testdata: 5 ~ 9, Score: 22
For Testdata: 10 ~ 14, Score: 33
For Testdata: 15 ~ 19, Score: 33
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 1000 65536 262144
16 1000 65536 262144
17 1000 65536 262144
18 1000 65536 262144
19 1000 65536 262144