SP6951 CTOI10D1 - MP3 Player

**MP3 播放器** Georg 的新 MP3 播放器有许多有趣的功能，其中包含按键锁定。在超过 $T$ 秒的时间里没有按键操作后，所有按键会自动被锁定。一旦锁定状态激活，任何按键都无法执行其正常功能，但随便按下一个键即会解除锁定。 举个例子，假设 $T = 5$ 且播放器当前为锁定状态。Georg 按下键 $A$，等待 3 秒，又按下键 $B$，等待 5 秒，再按键 $C$，再等 6 秒，最后按下键 $D$。在这个过程中，只有按键 $B$ 和 $C$ 执行了天然功能。这是因为在按键 $C$ 和 $D$ 之间的这段时间内，按键锁定了。 播放器的音量由 + 和 - 键控制，每次按 + 键增加音量 1 单位，按 - 键减少 1 单位。音量介于 0 和 $V_{\text{max}}$ 之间，达到上限或下限时，对应的按键不再有效。 ### 任务要求 Georg 不清楚具体的锁定时间 $T$。他想通过实验得出这个值。实验从锁定状态开始，他按下了 $N$ 次 + 和 - 键。在试验结束时，Georg 从播放器的显示上读到了最终音量。可惜的是，他忘记记录初始音量。题目中将未知的初始音量记为 $V_1$，已知的最终音量记为 $V_2$。 你需要计算能符合实验结果的最大可能整数值 $T$，还需提供一系列按键操作（+ 或 -）及其按下的时间（以秒为单位）。你的输入包括 $V_2$ 和按键顺序列表。这一列表详细列出按键类型和从实验开始算起的时间。这些按键的时间点是按降序排列的且相互不同。 ### 输入格式 第一行包含三个用空格分隔的整数：$N$、$V_{\text{max}}$ 和 $V_2$（其中 $0 \leq V_2 \leq V_{\text{max}}$）。接下来的 $N$ 行中，各行描述了按键序列中的一个按键：首先是一个字符 + 或 -，其次是一个整数 $C_i$（$0 \leq C_i \leq 2 \cdot 10^9$），表示从实验开始到此按键被按下经过的时间。可以确保这些按键按时间顺序排列且时间各不相同（即对于 $1 \leq i < N$，有 $C_i < C_{i+1}$）。 ### 数据范围与提示 保证 $2 \leq N \leq 100,000$ 且 $2 \leq V_{\text{max}} \leq 5,000$。 在特定测试样例中，有价值 40 分的情况下，保证 $N \leq 4,000$；价值 70 分的测试样例中，保证 $N \cdot V_{\text{max}} \leq 400,000$。 ### 输出格式 如果 $T$ 可以无限大，则输出一行为 `infinity`（引号仅用于说明）。 否则，输出一行，包含两个整数 $T$ 和 $V_1$，中间用空格分隔。 结果需要确保实验以锁定时间 $T$ 开始且初始音量 $V_1$，最终能得到音量 $V_2$。若有多个解，输出 $T$ 最大的一个；若仍有多个解，输出最大可能的 $V_1$。 （注：至少存在一个解，例如对于 $T = 0$ 情况，任何按键都不会生效，所以将 $V_1$ 设置为 $V_2$ 即可。） ### 示例 **输入:** ``` 6 4 3 - 0 + 8 + 9 + 13 - 19 - 24 ``` **输出:** ``` 5 4 ``` 对于 $T = 5$，按键依次执行操作：解锁，解锁，+，+，解锁，-。对于 $V_1 \in \{2, 3, 4\}$，最终音量都为 $V_2 = 3$。输出取可能最大的 $V_1$。 对于 $T \geq 6$，最后两次按键都会激活，所以音量无法达到 $V_2 = 3$。 **输入:** ``` 3 10 10 + 1 + 2 + 47 ``` **输出:** ``` infinity ``` 如果初始音量 $V_1 = 10$，无论 $T$ 是多少，最终音量都将是 $V_2 = 10$。 **本翻译由 AI 自动生成**

无

无