首页 > 试题广场 >

小游戏

[编程题]小游戏

热度指数：601 时间限制：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)