0109 飞镖游戏
* * * *
拉格朗日计划
* * * *
飞镖游戏

在飞镖游戏中,每轮玩家需向靶子上投掷三枚飞镖;靶子上有二十个面积相等的区域,每个区域分别标上了1至20中的一个数,作为该区域的分数。



每一枚飞镖的得分除了落点所在的区域外,还取决于它距离靶心的位置。落在外围的红/绿色圈以外(最外侧的黑环)时得零分,落在红/绿色圈以内的黑/白色区域时为一倍得分,落在外围和中间的红/绿色圈时分别为两倍和三倍得分。

在靶心处有两个同心圆,射中靶心外圆得25分,射中靶心内圈则得双倍即50分。

以下将分别用S、D、T代表单倍、双倍、和三倍分值,例如T10代表玩家射中了三倍的10分区域,得30分。

飞镖游戏的规则有许多变种,比较流行的是每个玩家从301分或501分开始,依次每轮投掷三枚飞镖并减去得分,首先在某一轮中将自己的分数减少到恰好为0的玩家获胜。通常还会采用“双倍结束”规则,即玩家的最后一镖必须射中一个双倍区域(包括双倍的靶心内圈,但不包括三倍区域)才能判定获胜。若某一镖的得分能使玩家的分数减少到1分以下,但并未射中双倍区域,则这一轮的得分都作废。

若玩家在某一轮开始的分数使之有可能在本轮中通过射中适当的区域而获胜,则这样的局面被称为“Checkout”。最高的“Checkout”局面为$170=T20+T20+D25$,玩家只需依次射中两个三倍20分和一个双倍靶心即可获胜。

6分是“Checkout”局面,此时共有11种获胜方式: $$\begin{matrix} D3 & & \\ D1 & D2 & \\ S2 & D2 & \\ D2 & D1 & \\ S4 & D1 & \\ S1 & S1 & D2 \\ S1 & T1 & D1 \\ S1 & S3 & D1 \\ D1 & D1 & D1 \\ D1 & S2 & D1 \\ S2 & S2 & D1 \\ \end{matrix} $$ 注意D1 D2和D2 D1是不同的获胜方式,因为两者最后一镖的双倍区域不同,而S1 T1 D1和T1 S1 D1则是相同的获胜方式。

此外,不考虑脱靶的情况,例如,D3、0 D3、以及0 0 D3都是相同的获胜方式。

在所有“Checkout”局面下一共有42336种不同的获胜方式。

对分数小于100的“Checkout”局面,一共有多少种不同的获胜方式?

本题难度:



解答

共有$20\times 3+3=63$个不同的得分区域(包括0分的情况),因此总共只有$63^3=250047$种可能性,暴力搜索即得结果$38182$。

import itertools
p=[str(i)+j for i in range(1,21) for j in "SDT"]+['0S','25S','25D']

def q(x):
    return int(x[:-1])*{"S":1,"D":2,"T":3}[x[-1]]

s=set([])
for i,j,k in itertools.product(p,repeat=3):
    if k[-1]=='D' and q(i)+q(j)+q(k) < 100:
        s.add((min(i,j),max(i,j),k))
print len(s)