首页 > 试题广场 >

小游戏

[编程题]小游戏

热度指数：600 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一天，小A和小B玩了一个神奇的游戏，游戏开始时，桌面上有a₀个不同盒子和b₀个不同的物品，每个回合，两个人可以选择增加一个新的盒子或者一个新的物品(所有物品和盒子都不同)，记当前桌子上的盒子数量为a，物品数量为b，当把b个物品放入a个盒子的方案数不小于n时，游戏结束，此时最后一位操作者判负。

给出a₀，b₀，n，如果小A先手，两个人都采用最优策略，谁能获胜，如果A获胜输出“A”，如果B获胜，输出“B”，如果是平局，输出“A&B”。

输入描述:

输入第一行是一个数据组数T(T<=10)。
接下来T行，每行描述一个测试数据，包含三个整数a₀,b₀,n(1<=a₀<=10000,1<=b₀<=30,2<=n<=10^9)。分别表示桌子上初始的盒子数，球数和n值。

输出描述:

对于每个测试数据，输出一行，仅包含一个字符串，即“A”，“B”或“A&B”。

示例1

输入

输出

B
A
A&B

算法知识视频讲解

Python

niyn

虽然只通过了73.33%，还是写下来，就当加深了，思路如下：

两种选择：(a+1,b) or (a,b+1)

1.在都小于n的基础上，尽可能选max(pow(a+1,b),pow(a,b+1))，根据选择，更新目前盒子和物品的数量，继续下一个。

2.其中一个不小于n的话，只能选另一个小于n的，这里判断平局的情况：

当a==1，且pow(a+1,b)>=n的话，只能选b+1，这样陷入死循环，敌不动我不动，1的任何次方都是1，大家都是一样的n

3.都不小于n的话，当前操作的人输了

N=int(input())
import math
def cal(box,goods):
    return math.pow(box,goods)
for i in range(N):
    a,b,n=list(map(int,input().split()))
    if cal(a,b)>=n:
        print("B")
        break
    temp=cal(a,b)
    order=["A","B"]
    i=0
    while True:
        c1=cal(a+1,b)
        c2=cal(a,b+1)
        if c1<n and c2<n:
            if c1>c2:
                temp=c1
                a+=1
            else:
                temp=c2
                b+=1
        elif c1>=n and c2<n:
            if temp==c2:
                print("A&B")
                break
            temp=c2
            b+=1
        elif c2>=n and c1<n:
            if temp==c1:
                print("A&B")
                break
            temp=c1
            a+=1
        else:
            print(order[i%2])
            break
        i+=1

编辑于 2020-08-09 10:29:17 回复(2)

石头君

感觉这题有问题，什么叫最优思路啊。

发表于 2019-06-24 11:48:58 回复(0)

(*^__^*)……

这道题的答案是有问题的，当a0=1时，不可能存在B获胜的情况，因为当a0=1，A只有让a0+1，才有可能让B失败，然而如果这样子做还让B赢了，那么A肯定不可能让a0+1，但答案中只要你a0^b0<n,就强行让A执行a0+1。

发表于 2019-07-08 15:17:15 回复(0)

OAQ

最高只通过了53.33%，但我总觉得测试样例有点问题，比如说(1,9,8558)，按我的思路应该是A胜，但答案给的B胜，不知道是我哪里想错了...记录一下思路，抛砖引玉吧

主要思路：

0.首先，对（a,b），有pow(a,b)种放法

1.这个游戏最重要的一点是，A先手，且两人都采取最优策略。可以把这个游戏想象成一大棵决策树，每个节点表示(a,b)，其子节点为(a+1,b),(a,b+1),那么当某个节点的两个子节点都大于n时，该叶节点对应的操作人就是获胜方。所以两个人希望的是，当自己操作完某个步骤以后，以这个步骤对应的节点为根的子树的叶节点的获胜方都是自己

2.根据以上思路：

(1)平局: 当a==1，且pow(a+1,b)>=n时，平局，因为这时候A只能令b+1，否则A输了。当pow(a+1,b)<n时，A可以把状态转化为(a+1,b)，如果这个状态A必胜，那么就可以不必平局。所以还需要进一步讨论。

首先用count=0表示当前步数,那么count%2==0时该A走，否则该B走，用于判断操作人

(2)当pow(a+1,b)>=n但pow(a,b+1)<n时，两人都只能往b上加1，所以最终谁胜很容易计算，maxb=int(log(n,a))，所以最多还能走maxb-b个回合，判断(maxb-b+count)%2即可(需要注意的是，log(n,a)为整数时，maxb应减1，因为走maxb步刚好等于n就输了)

(3)同理pow(a+1,b)<n但pow(a,b+1)>n时，a最多加到maxa=int(pow(n,1/b))，所以判断(maxa-a+count)%2即可(同样有pow(n,1/b)的问题)

(4)关键问题：当pow(a+1,b)和pow(a,b+1)都<n怎么办？我考虑用的dfs，但可能是有问题的，说一下我的思路:

令addA = dfs(a+1,b,n,count),addB=dfs(a,b+1,n,count)，那么当该A操作时，如果addA或者addB任意一个为'A'胜，那么A就可以相应的操作让自己赢，B同理。但如果A发现addA和addB操作自己都要输，那dfs(a,b,n,count)的状态就应该为输(count=0时返回B，为1时返回A)

以下代码：（也请大佬帮忙看看哪错了...

import sys
import math
try:
    while True:
        t = sys.stdin.readline().strip()
        if t == '':
            break
        for _ in range(int(t)):
            a,b,n = [ int(i) for i in sys.stdin.readline().strip().split()]
            if a==1 and pow(2,b)>=n:
                print 'A&B'
            else:
                def dfs(a,b,n,flag):
                    if a==1 and pow(a+1,b)<n:
                        tt = dfs(a+1,b,n,flag+1)
                        if tt == 'A':
                            return 'A'
                        else:
                            return 'B'
                    temp1 = pow(a+1,b)
                    temp2 = pow(a,b+1)
                    if temp1 >= n:
                        if temp2 >= n:
                            return 'B' if flag%2 else 'A'
                        else:
                            maxB = int(math.log(n,a))-b
                            if math.log(n,a)%1==0:
                                maxB += 1
                            return 'B' if (maxB+flag)%2 else 'A'
                    elif temp2 >= n:
                        maxA = int(pow(n,1.0/b))-a
                        if pow(n,1.0/b)%1 == 0:
                            maxA += 1
                        return 'B' if (maxA+flag)%2 else 'A'
                    else:
                        addA = dfs(a+1,b,n,flag+1)
                        addB = dfs(a,b+1,n,flag+1)
                        if flag%2 == 0 and addA == 'A' or addB == 'A':
                            return 'A'
                        elif flag%2 == 1 and addA == 'B' or addB == 'B':
                            return 'B'
                        else:
                            if flag%2:
                                return 'B'
                            else:
                                return 'A'
                print dfs(a,b,n,0)
except:
    pass

编辑于 2019-07-14 19:33:40 回复(0)