问题描述

塔子哥和他的好朋友在玩一个魔法宝石的游戏。游戏开始时，有一颗魔法宝石，其能量值为 $x$。每回合，塔子哥可以给宝石注入能量值在 $[a, b]$ 之间的能量，而他的朋友可以注入能量值在 $[c, d]$ 之间的能量。当宝石的能量值大于等于 $s$ 时，游戏结束，最后一个操作宝石的人将获得胜利。

题解

在笔试中为数不多的博弈论的题，一般碰到这种类型的题一般有以下三种解法：

1. 猜结论
2. 动态规划
3. 求 sg 函数

由于这题数据范围比较小，我们直接 DP 即可。