uoj#P160. 【清华集训2015】斗地主
【清华集训2015】斗地主
这是一道提交答案题。
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用A到K加上大小王的来进行的扑克牌游戏,其中,A到K(分别用A、2、3、4、5、6、7、8、9、T、J、Q、K表示)各四张,大小王(用w表示小王,W表示大王)各一张。
牌的大小关系如下:3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A < 2 < w< W
牛牛在noip中知道了每副手牌最少需要多少次才能出完。然而,他又被小伙伴们嘲笑了一番,因为能否赢得一局游戏似乎跟手上的牌多少次能出完没有什么关系,而且他居然不知道飞机可以带翅膀。现在牛牛又在跟小伙伴打牌,
牛牛或小伙伴每次可以按照规定的牌型进行出牌,并在对手打光手牌之前打光自己的手牌以取得游戏的胜利,同时,胜利的一方可以得到 $x$ 的奖励,失败的一方受到 $x$ 的惩罚,$x$ 为胜利方打光手牌时失败方剩余牌的数量。
牌型规定如下:
牌型 | 牌型说明 | 牌型举例 |
---|---|---|
火箭 | 即双王(大王+小王) | wW |
炸弹 | 四张同点牌。如四个A。 | AAAA |
单个牌 | 单张牌,比如3。 | 3 |
对子牌 | 两张点数相同的牌。 | 44 |
三张牌 | 三张点数相同的牌。 | 555 |
三带一 | 三张同点牌 + 一张单牌。例如:三张3+单4 | 3334 |
三带二 | 三张同点牌 + 一对牌。例如:三张3+对4 | 33344 |
单顺子 | 五张或更多连续的单牌。例如:单3+单4+单5+单6+单7。不能包括2点和王。 | 34567 |
双顺子 | 三对或更多连续的对子牌。例如:对3+对4+对5。不能包括2点和双王。 | 334455 |
三顺子 | 二个或更多连续的三张牌。例如:三张3+三张4+三张5。不包括2点和双王。 | 333444555 |
四带二 | 四张同点牌+任意两张单牌,例如:四张5+单3+单8 | 555538 |
四带两对 | 四张同点牌+任意两个对子牌,例如:四张4+对5+对7 | 44445577 |
飞机带翅膀 | 三顺子+同数量的单牌。 | 3334445559QK |
飞机带双翅膀 | 三顺子+同数量的对牌。 | 7778889993366QQ |
比较大小的规则如下:
- 一般地,只在同种牌型同样张数的情况下,才可以比较大小。
- 对单个牌,对子牌,三张牌,单顺子,双顺子,三顺子,比较其中最大的一张牌的点数。
- 对于三带一、三带二,比较其中三张同点牌的大小。
- 对于四带二,四带两对,比较其中四张同点牌的大小。
- 对于飞机带翅膀和飞机带双翅膀,比较其中三顺子的大小。
- 特殊地,火箭大于任何牌。
- 特殊地,炸弹大于除了火箭和点数超过自己点数的其他炸弹之外的任何牌。
一开始由牛牛先出牌,可以打出任意符合如上规则的牌。
当一方打出牌后,对方可以有以下两种选择:1、出一手比对方大的牌。2、放弃出牌。
当一方放弃出牌时,对方继续出牌,打出任意一种牌型的牌。
当一方打出手上最后的牌时,立即停止上述一切操作,游戏立即结束,并计算奖惩
牛牛和小伙伴都通过某种特殊方法知道了对方手上的所有牌,并且他们都知道对方知道自己的牌。
他们都希望自己能获得尽量多的奖励及受到尽量少的惩罚。
由于牛牛的小伙伴非常地机智,不会出现任何失误,请你帮牛牛算一算,对于当前这一副牌,他能否获得胜利,如果能,求出最大能获得多少奖励,如果不能,求出最少需要受到多少惩罚。
输入格式
每个测试点包含若干组数据,以 0 0
结尾。
每组数据第一行包含两个正整数,分别表示牛牛手上牌的数量和小伙伴手上牌的数量。
每组数据的第二行包含一个字符串,每个字符表示牛牛手上的牌的点数。
每组数据的第三行包含一个字符串,每个字符表示小伙伴手上的牌点数。
输出格式
对于每组数据,如果牛牛能获胜,输出一个整数 $x$,$x$ 表示他最多能获得多少奖励,如果牛牛不能获胜,输出一个整数 $-x$,$x$ 表示他最少要受到多少惩罚。
样例一
见 sample.in
和 sample.out
。
限制与约定
保证给出的双方的牌是合法的。 本题按照正确率给分,对于一个测试点,如果你的正确率为p,那么得分为$\lfloor 20p^3 \rfloor$
注意,在比赛时本题的测评方式为直接判0分。