題目 1949:
藍(lán)橋杯算法提高VIP-House of Cards
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 3 解決: 0
題目描述
Axel和Birgit喜歡玩這樣的一種紙牌游戲：他們建造一個(gè)由紙牌組成的房子，當(dāng)他們添加紙牌到房子的時(shí)候，會(huì)獲得（或失去）游戲的分?jǐn)?shù)。由于他們都有一雙靈巧的手，紙牌組成的房子是不會(huì)倒塌的。他們使用半副標(biāo)準(zhǔn)紙牌。一副標(biāo)準(zhǔn)的紙牌有4種花色，2種是紅色，2種是黑色。Axel和Birgit只使用2種花色，1紅1黑。每種花色有13個(gè)等級(jí)。我們使用記號(hào)1R，2R，…，13R，1B，2B，…，13B來(lái)表示等級(jí)和顏色。
開(kāi)始前，玩家要選擇半副標(biāo)準(zhǔn)紙牌的一個(gè)子集，子集中所有紙牌的最大等級(jí)是M。洗完選出的紙牌后，他們從牌堆的最上面拿出8張，從左到右連續(xù)地放置它們形成4個(gè)“山峰”。舉個(gè)例子，如果M=13而且前10張紙牌（26張的前10張）是：
6B 3R 5B 2B 1B 5R 13R 7B 11R 1R …
那么這個(gè)游戲開(kāi)始的時(shí)候就像圖7所展示的那樣。
剩下的紙牌正面朝上被放置成一排。
每個(gè)玩家被認(rèn)定一種顏色，紅色或黑色。Birgit總被認(rèn)定是黑色，Axel總被認(rèn)定是紅色。第一張用于組成山峰和山谷的紙牌的顏色決定了哪個(gè)玩家先開(kāi)始。圖7的那個(gè)例子，Birgit先開(kāi)始，因?yàn)榈谝粡埣埮剖?B。
玩家交替進(jìn)行操作。一步操作包括從一排紙牌的最前面抽取一張紙牌然后進(jìn)行下列的一條：
1．持有這張紙牌直到下次操作（這是一張“被持有的紙牌”）。
2．用剛抽取的紙牌或被持有的紙牌覆蓋在兩個(gè)山峰之間的山谷，形成一個(gè)“基底”。如果還剩下一張牌，那么這張牌就被持有。
3．把2張紙牌放在基底上面，形成一個(gè)山峰（其中一張紙牌一定是一張被“持有”的紙牌）。
不是所有的選擇總是可行的。任何時(shí)候最多持有1張紙牌，所以第一個(gè)選擇只有當(dāng)這個(gè)玩家沒(méi)有持有紙牌時(shí)才可行。
因?yàn)榕懦梢慌诺募埮剖钦娉希詢(xún)蓚€(gè)玩家在紙牌被抽取前就事先知道紙牌的順序。
如果玩家通過(guò)添加了一個(gè)基底組成了一個(gè)向下的三角形，或者通過(guò)添加了一個(gè)山峰組成了一個(gè)向上的三角形，那么玩家的分?jǐn)?shù)就會(huì)像下面描述的那樣更新。組成三角形的3張紙牌的等級(jí)之和將被增加到那個(gè)顏色與3張紙牌的多數(shù)顏色相等的那個(gè)玩家的分?jǐn)?shù)上。如果在游戲中沒(méi)有組成三角形，兩個(gè)玩家的分?jǐn)?shù)保持不變。
圖7的那個(gè)例子，如果Birgit放置她的紙牌（11R）到中間的山谷上，她將獲得14分。如果她放置她的紙牌到左邊的山谷上，Axel獲得19分。如果她放置她的紙牌到右邊的山谷上，Axel獲得29分。
如果在某步操作結(jié)束后沒(méi)有紙牌等待被抽取，這個(gè)游戲就結(jié)束了。如果某個(gè)玩家在這個(gè)時(shí)候持有紙牌，那個(gè)玩家的分?jǐn)?shù)將會(huì)增加（或減少）這張紙牌的等級(jí)如果這張紙牌的顏色與玩家顏色相同（不同）。
當(dāng)這個(gè)游戲結(jié)束后，分?jǐn)?shù)低的玩家將要支付一定數(shù)量的瑞典克朗給另一個(gè)玩家，數(shù)量等同于兩個(gè)玩家的分?jǐn)?shù)差。如果是平局，就不用支付。
你必須寫(xiě)一個(gè)程序讀入一副被洗過(guò)的牌堆和一個(gè)玩家的名字，然后找出這個(gè)玩家最多能贏多少（或者最少能輸多少），假設(shè)另一個(gè)玩家總是采取最優(yōu)策略。
開(kāi)始前，玩家要選擇半副標(biāo)準(zhǔn)紙牌的一個(gè)子集，子集中所有紙牌的最大等級(jí)是M。洗完選出的紙牌后，他們從牌堆的最上面拿出8張，從左到右連續(xù)地放置它們形成4個(gè)“山峰”。舉個(gè)例子，如果M=13而且前10張紙牌（26張的前10張）是：
6B 3R 5B 2B 1B 5R 13R 7B 11R 1R …
那么這個(gè)游戲開(kāi)始的時(shí)候就像圖7所展示的那樣。
剩下的紙牌正面朝上被放置成一排。
每個(gè)玩家被認(rèn)定一種顏色，紅色或黑色。Birgit總被認(rèn)定是黑色，Axel總被認(rèn)定是紅色。第一張用于組成山峰和山谷的紙牌的顏色決定了哪個(gè)玩家先開(kāi)始。圖7的那個(gè)例子，Birgit先開(kāi)始，因?yàn)榈谝粡埣埮剖?B。
玩家交替進(jìn)行操作。一步操作包括從一排紙牌的最前面抽取一張紙牌然后進(jìn)行下列的一條：
1．持有這張紙牌直到下次操作（這是一張“被持有的紙牌”）。
2．用剛抽取的紙牌或被持有的紙牌覆蓋在兩個(gè)山峰之間的山谷，形成一個(gè)“基底”。如果還剩下一張牌，那么這張牌就被持有。
3．把2張紙牌放在基底上面，形成一個(gè)山峰（其中一張紙牌一定是一張被“持有”的紙牌）。
不是所有的選擇總是可行的。任何時(shí)候最多持有1張紙牌，所以第一個(gè)選擇只有當(dāng)這個(gè)玩家沒(méi)有持有紙牌時(shí)才可行。
因?yàn)榕懦梢慌诺募埮剖钦娉希詢(xún)蓚€(gè)玩家在紙牌被抽取前就事先知道紙牌的順序。
如果玩家通過(guò)添加了一個(gè)基底組成了一個(gè)向下的三角形，或者通過(guò)添加了一個(gè)山峰組成了一個(gè)向上的三角形，那么玩家的分?jǐn)?shù)就會(huì)像下面描述的那樣更新。組成三角形的3張紙牌的等級(jí)之和將被增加到那個(gè)顏色與3張紙牌的多數(shù)顏色相等的那個(gè)玩家的分?jǐn)?shù)上。如果在游戲中沒(méi)有組成三角形，兩個(gè)玩家的分?jǐn)?shù)保持不變。
圖7的那個(gè)例子，如果Birgit放置她的紙牌（11R）到中間的山谷上，她將獲得14分。如果她放置她的紙牌到左邊的山谷上，Axel獲得19分。如果她放置她的紙牌到右邊的山谷上，Axel獲得29分。
如果在某步操作結(jié)束后沒(méi)有紙牌等待被抽取，這個(gè)游戲就結(jié)束了。如果某個(gè)玩家在這個(gè)時(shí)候持有紙牌，那個(gè)玩家的分?jǐn)?shù)將會(huì)增加（或減少）這張紙牌的等級(jí)如果這張紙牌的顏色與玩家顏色相同（不同）。
當(dāng)這個(gè)游戲結(jié)束后，分?jǐn)?shù)低的玩家將要支付一定數(shù)量的瑞典克朗給另一個(gè)玩家，數(shù)量等同于兩個(gè)玩家的分?jǐn)?shù)差。如果是平局，就不用支付。
你必須寫(xiě)一個(gè)程序讀入一副被洗過(guò)的牌堆和一個(gè)玩家的名字，然后找出這個(gè)玩家最多能贏多少（或者最少能輸多少），假設(shè)另一個(gè)玩家總是采取最優(yōu)策略。
輸入格式
讀入包含多組測(cè)試數(shù)據(jù)代表多個(gè)游戲。每組測(cè)試數(shù)據(jù)包含一個(gè)名字（Axel或者Birgit），然后會(huì)有1個(gè)最大的等級(jí)M（5 ≤ M ≤ 13），緊接著有2M張紙牌的等級(jí)和顏色，按在牌堆中的位置給出。每一個(gè)等級(jí)（從1到M）和顏色的組合在序列中只會(huì)出現(xiàn)一次。初始序列的前8張按抽出的順序從左到右組成山峰，剩下的顯示了紙牌的順序。
包含單詞End的一行緊跟在最后一組數(shù)據(jù)后面。
包含單詞End的一行緊跟在最后一組數(shù)據(jù)后面。
輸出格式
對(duì)于每個(gè)測(cè)試數(shù)據(jù)，輸出數(shù)據(jù)的編號(hào)（從1開(kāi)始），這組數(shù)據(jù)中玩家的名字，和這個(gè)玩家贏或輸了多少分?jǐn)?shù)。如果是平局，指出是平局而不是輸出數(shù)字。參照樣例輸出的格式。
樣例輸入
Axel 5 1R 2R 3R 4R 5R 5B 4B 3B 2B 1B Birgit 5 1R 2R 3R 4R 5R 5B 4B 3B 2B 1B Birgit 5 1R 1B 3R 4R 5R 5B 4B 3B 2R 2B End
樣例輸出
Case 1: Axel wins 1 Case 2: Birgit loses 1 Case 3: Axel and Birgit tie
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情