ACM竞赛第十题.docx

10-20-30有一种称为10—20—30的用52张不考虑花色的纸牌游戏。人头牌(K、Q、J)的值是10，A的值是1，任何其他牌的值是它们的面值(如2、3、4等)。牌从牌堆的顶端发起。你先发7张牌，从左至右形成7组。当给最右边一组发了一张牌后，下一张牌就应发最左边的一组。每给一组发一张牌时，查看这组牌的以下三张牌的组合的总和是否为10、20或30： 前两张和最后一张， 第一张和最后二张，或 最后三张。如果是这样，就抽出这三张牌并将其放在牌堆的底部。对于这个问题，总是按上面给出的顺序查看牌。按牌在组中出现的顺序将它们取出并放在牌堆的底部。当抽出三张牌时，又有可能出现三张可以抽出的牌。如果是这样，再将它们抽出。如此重复直至再也不能从这组牌抽出符合条件的牌为止。举例来说，假设有组牌含5、9、7、3，5是第一张牌，然后发出6。前两张牌加最后一张牌(5+9+6)等于20。抽出这三张牌后这组牌成为7、3。而牌堆的最底部变成6，6上面的一张牌是9，9上面的一张牌是5(如图6.2-1)。图6.2-1如果发的不是6而是Q，那么5+9+10=24，5+3+10=18，但7+3+10=20，因此最后三张牌可以抽走，剩下5、9(如图6.2-2)。图6.2-2如果有一组只含有三张牌且这组牌的和为10、20或30，那么这组牌被抽走后就“消失”了。这就是说，随后的发牌将跳过现在成为空的这组牌的位置。当所有牌组都消失，你就获胜。当你无牌可发时，你游戏失败。当前两种情况都不发生时，出现平局。编写一个程序，将初始的牌堆作为输入，完成10—20—30游戏。输入每组输入由52个整数组成，由空格和／或行结束(end 0f line)分开。整数表示初始牌堆的面值。第一个整数是牌堆的最顶端的牌。在最后一张牌后输入0标志输入结束。输出对每组输入，输出游戏结果是胜、负还是平局，并输出游戏结果决定前所发的牌数。(假如游戏状态发生重复，意味着平局)使用“输出范例”部分中表明的格式。输入范例输出范例2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 110 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2 4 3 2 10 8 10 6 8 9 5 8 10 5 3 5 4 6 9 9 1 7 6 3 5 10 10 8 10 9 10 10 72 6 10 10 4 10 1 3 10 1 1 10 2 2 10 4 10 7 7 1010 5 4 3 5 7 10 8 2 3 9 10 8 4 5 1 7 6 7 2 6 9 10 2 3 10 3 4 4 9 10 1 110 5 10 10 1 8 10 7 8 10 6 10 10 10 9 6 2 10 10 0Win：66Loss：82Draw：73试题来源：ACM 1996总决赛在线测试地址：UVA 246试题解析 我们将游戏过程中手中牌和各堆牌的状况用字符串s表述分隔定位每堆牌的区间 我们将7堆牌和手中的牌转化为字串s，并通过大写字母”ABCDEFGH”分割的办法定位每堆牌的位置。例如，初始时输入52张牌的面值a[1..52]，则s=”Aa[1]Ba[2]Ca[3]Da[4]Ea[5]Fa[6]Ga[7]Ha[8..52]”。a[1..7]为最先放入牌堆1‥牌堆7的七张牌，手中的牌为a[8..52]，并将之定义为牌堆8。为了定位每堆牌在s中的首尾位置设sign[i]为第i堆的标志（sign[1]=‘A’, …, sign[7]=‘G’，sign[8]=‘H’），该堆牌在s中的首尾指针为l[i]和r[i]。显然，l[i]为s中字符sign[i]的位置+1；r[i]为s中字符sign[i+1]的位置-1。⑵使用哈希技术判别重合情况我们将字串s设为状态。显然，当前状态若与先前状态重合，则说明继续玩下去是不可能有输赢的，应视为平局。为此，我们使用哈希技术存储当前状态。状态s的哈希函数设为hash(s)=若不考虑花色的话，纸牌共有13个不同种类，我们将s中的每一位数码看作是一个13进制数。hash(s)取s对应的13进制数对素数1999997（小于哈希表长的最大素数）的余数。但这个哈希函数并不完全可靠，因为不能保证哈希值与状态一一对应。为此，我们采用开放寻址法消除冲突：将hash(s)设为哈希表中有哪些信誉好的足球投注网站状态s的首址；另外再设状态s的判重函数hash2(s)，该函数值取s对应的13进制数对素余数，即hash2(s)=只有当hash(s1)=hash(s2)，hash2(s1)=hash2(s2)时，才可确定状态s1和s2相同。哈希表为h和key，其中h[f]为状态存储标志。若h[f]