CF2157F Git Gud

你是一名为未来公司 RoboCorp 工作的冒险者。你当前的技能等级为整数 $s$，范围在 $[1, n]$，但你并不知道其具体值。你的目标是通过为 RoboCorp 完成任务，使你的技能提升到 $n$ 或更高，但每次执行任务都需要花费宝贵的 robocoin。 你可以选择任意难度和任意正整数时长（小时）的任务。然而，任务的花费既取决于新任务的持续时间，也与本次任务和你上一次任务的难度比较有关。 设 $x$ 为你最近一次任务的难度。如果你要选择一个新任务，难度为 $y$，时长为 $l$： - 如果这是你的第一项任务，或者 $y \leq x$，则花费 $l$ robocoin。 - 如果 $y > x$，则花费 $1000 + l$ robocoin。 你的技能只会在任务难度与当前技能值精确匹配时提升： - 如果 $y = s$，那么你的技能提升 $l$。 - 否则你的技能不会变化。 每次任务结束后，你依然不知道自己的实际技能值。 你一开始拥有 $10^6$ robocoin。请你设计一个策略（即一系列任务），保证无论初始技能值如何，最终你的技能一定可以达到 $n$ 或更高，并且总花费不超过预算。

输入包含一行一个整数 $n$（$n=4$ 或 $n=250\,000$），表示目标技能等级（即最终你的技能要达到 $n$ 或更高）。 本题总共包含 2 个测试点（包括示例）。示例为 $n=4$，另一个测试点为 $n=250\,000$。 本题不允许 hack。

第一行输出一个整数 $k$（$0 \leq k \leq 10^6$），表示你计划需要完成的任务数量。 接下来 $k$ 行，每行输出两个整数 $y$ 和 $l$（$1 \leq y, l \leq 10^6$），表示第 $i$ 项任务的难度与时长（小时）。

以示例为例，目标技能等级 $n=4$。你可以采用如下策略： - 首先执行一次难度 $y=1$、时长 $l=4$ 的任务。因为是第一次任务，仅需支付 $l=4$ robocoin。 - 执行难度 $y=3$、时长 $l=1$ 的任务。上次难度 $x=1$，由于 $y>x$，需要支付 $l+1000=1001$ robocoin。 - 接着执行难度 $y=2$、时长 $l=1$ 的任务。由于 $y\leq x$，只需支付 $l=1$ robocoin。 - 再次执行难度 $y=3$、时长 $l=1$ 的任务。此时 $y>x$，需支付 $l+1000=1001$ robocoin。 合计花费 $2007$ robocoin，未超出 $10^6$ robocoin 预算。 我们验证该策略始终有效： - 若初始技能为 $1$，第一项任务过后技能变为 $5$。 - 若初始技能为 $2$，到第三项任务后技能为 $3$，第四项任务后技能升为 $4$。 - 若初始技能为 $3$，第二项任务后技能升为 $4$。 - 若初始技能为 $4$，技能值始终为 $4$。 所以无论初始技能如何，最终你的技能都能达到 $n$。 由 ChatGPT 5 翻译