SP18438 VAL_GAM4 - Happy Valentine Day (Valentine Adventure Game)
题目描述
情人节快乐！在这个问题中，你将玩一个冒险游戏，需要在一维虚拟世界中把巧克力带回家。你的起点是位置 0，家位于位置 **h**。在从 0 前往 **h** 的旅途中，你可能会遇到一些想要偷你的巧克力的坏人，因此你需要与他们战斗。如果你赢了，就可以继续旅程，否则你必须重新开始。沿途还有一些旗帜可以获取，如果你成功拿到旗帜，重新开始游戏时会从那个旗帜位置继续，但之前的旗帜将会消失，需要重新获取。如果获得了多个旗帜，会从最近获取的旗帜位置继续，其他获得的旗帜仍会保留。
现在你需要根据给定的地图，计算完成游戏所需的期望时间。地图中标出了所有旗帜的位置及其成功获取的概率、所有战斗发生的位置及胜率、以及你家的位置。假设你的移动速度是恒定的：每单位时间移动 1 个单位距离，并且进行战斗和获取旗帜时不消耗时间。
输入格式
文件中包含多个测试用例：
- 每个测试用例的第一行由两个整数 **h** 和 **q** 组成，分别表示家的位置和 0 到 **h** 之间的物体数量。
- 随后的 **q** 行中，每行包含一个字符和三个整数：**c**、**n**、**a**、**b**：
- **c** 表示物体的类型（'X' 表示战斗，'F' 表示旗帜）。
- **n** 表示物体的位置，位置保证严格递增（即大于前一个 **n**）。
- **a** 和 **b** 分别表示概率的分子和分母，因此概率为 **a**/**b**。
输入的最后一行是两个零，表示测试用例的结束，你的程序应在此时终止。
输出格式
对于每个测试用例，输出完成游戏所需的期望时间。由于结果可能非常大，请对 10 $ ^9 $ +7 取模后输出。所有测试用例保证期望时间均为整数。
**本翻译由 AI 自动生成**