A和B在玩一個(gè)射擊游戲,戰(zhàn)場(chǎng)由若干單位正方形積木組成。積木占據(jù)了連續(xù)的若干列,且圖形周長(zhǎng)等于它最小包圍矩形的周長(zhǎng)。下圖(a)是一個(gè)合法的戰(zhàn)場(chǎng),但(b)和(c)都不是:(b)中有空列;(c)的圖形周長(zhǎng)為14,而最小包圍矩形(用虛線畫出)的周長(zhǎng)為12。受重力影響,每個(gè)積木的正下方要么是地面,要么是另一個(gè)積木。為了讓戰(zhàn)場(chǎng)看上去錯(cuò)落有致、玩著更刺激,它不能恰好是一個(gè)矩形(即:不能每列積木都一樣高)。
游戲規(guī)則如下:
1、 A和B輪流射擊,A先射擊。
2、 每次射擊時(shí),首先選擇一行(該行必須至少有一個(gè)積木),以及“左”和“右”中的一個(gè)方向,然后往這個(gè)方向開火。子彈的威力為1~3的均勻隨機(jī)整數(shù)(即:威力為1、2、3的概率各為1/3),表示子彈能打掉的積木個(gè)數(shù),被打掉的積木將直接從戰(zhàn)場(chǎng)中消失。如果該行的積木個(gè)數(shù)小于威力值,則子彈將在打掉該行所有積木后消失。例如,若選擇往右射擊從下往上數(shù)第3行,且威力為2,且這一行一共有4個(gè)積木,則最左邊的兩個(gè)積木將被打掉。注意:這兩個(gè)積木可以不連續(xù)。
3、 每次射擊完成后,懸空的積木垂直往下落。所有積木不再下落后,下一位選手才能開始射擊。
4、 誰(shuí)打掉了最后一個(gè)積木,誰(shuí)就獲勝。
假定開局是,根據(jù)規(guī)則1,A先開火。射擊后,B可能面臨的后續(xù)局面中的其中三個(gè)如下表:
行編號(hào)(從下往上數(shù)) |
子彈前進(jìn)方向 |
威力(隨機(jī)值) |
剛射擊后 |
積木穩(wěn)定后 |
2 |
從右往左 |
1 |
|
(同左圖) |
1 |
從右往左 |
2 |
|
|
1 |
從左往右 |
3 |
|
|
假定A和B都足夠聰明,采取讓自己獲勝概率盡量高的策略,你的任務(wù)是計(jì)算出A獲勝的概率。
輸入文件最多包含25組測(cè)試數(shù)據(jù),每個(gè)數(shù)據(jù)僅包含兩行,第一行是整數(shù)n(1<=n<=6),即積木的列數(shù)。第二行包含n個(gè)正整數(shù)h1, h2,..., hn(1<=hi<=6),表示從左往右數(shù)第i列的高度。積木的排列方式保證符合題目描述(即:圖形周長(zhǎng)等于它最小包圍矩形的周長(zhǎng),且各列的高度不全相同)。n=0表示輸入結(jié)束,你的程序不應(yīng)當(dāng)處理這一行。
3 2 1 1 0
0.555556
Tips:
請(qǐng)對(duì)本次比賽進(jìn)行一些描述,公告內(nèi)容應(yīng)當(dāng)包含:
比賽的創(chuàng)辦者或組織;
本次比賽的目的或意義;
本次比賽的考點(diǎn)、語(yǔ)言或類型;或其他注意事項(xiàng)及描述等。
至少保證30個(gè)漢字長(zhǎng)度。