题解 | 扩展巴什博弈(清晰注释)

【模板】扩展巴什博弈

https://www.nowcoder.com/practice/4b0d36a3d3884cf69f618cf4c2511d82

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n, l, r = map(int, sys.stdin.readline().split())
    
    cycle = l + r  # 一个完整的取石子周期
    remain = n % cycle
    
    # 如果剩余石子不足l,先手无法控制局面
    if remain < l:
        print("NO")
    else:
        print("YES")

"""
设 remain = n % (l + r)
1. 若 remain < l
   无论A取 x∈[l,r], B只需要取(l+r - x)就能保证余数 < l
   最后轮到 A 时剩余石子数量 < l, A必败
  
2. 若 remain 在[l, r]区间内, A只需要取走remain即可
   此时剩余石子余数为 0
   之后无论B取 y∈[l,r],A都取 (l+r - y),保证剩余石子的余数 为 0
   最后轮到 B 时剩余石子数量为 0, A必胜
  
3. 若 remain 在[r+1, l+r]区间内, A取走 r,使剩余石子为 n - r
   此时剩余石子余数为 (n - r) % (l + r) = remain - r < l
   之后无论B取 y∈[l,r],A都取 (l+r - y),保证剩余石子的余数 < l
   最后轮到 B 时剩余石子数量 < l, A必胜
"""

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 20:49
某国企 研发工程师 31W 硕士211
点赞 评论 收藏
分享
10-01 09:50
门头沟学院 Java
肖先生~:这个人真的很好,点赞
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务