首页 > 试题广场 >

炸弹游戏

[编程题]炸弹游戏

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

Alice和Bob相约一起玩一个炸弹游戏。

游戏开始时，Alice手上拿着一个定时炸弹，炸弹有个倒计时t。炸弹在t=0时刻会爆炸，此时手上拿着炸弹的人就输了。为了增加游戏乐趣，他们约定每个人拿到炸弹后可以选择将炸弹的时间调快d秒(d ∈ [a,b])，或者不调。每次交换炸弹会消耗1秒（假设调节炸弹时间不需要消耗时间）。

问题来了，如果双方都足够聪明，谁会赢呢？

输入描述:

第一行有三个整数t,a,b，分别表示炸弹初始时刻的倒计时，可调节时间的范围。(0 ≤ t ≤ 10⁵,1 ≤ a ≤ b ≤ 10)

输出描述:

若Alice赢则输出"Alice"，若Bob赢则输出"Bob"。

示例1

输入

6 3 4

输出

Alice

说明

Alice只需要将炸弹调快3秒后再给Bob，Bob就会拿到一个2秒后爆炸的炸弹。

算法知识视频讲解

小琢卷不动

发表于 2021-11-23 22:19:46

基础的博弈论，如果我可以通过一个状态让对方必死，我就能活；反之我必死。值得注意的是：调快 [a,b][a,b][a,b] 秒，也可以不调。据此设 life(x)life(x)life(x) 表示剩余 xxx 秒时先手是否能活，加一个记忆化即可保证每个状态的计算只进行一次，据此复杂度为 O( 展开全文