TopCoder

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

User's AC Ratio

50.0% (7/14)

Submission's AC Ratio

10.0% (11/110)

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

No. Testdata Range Score
1 0~4 12
2 5~9 22
3 10~14 33
4 15~19 33

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4