← 返回题目列表

Codeforces · 2157/F

F. 练好 Git 技巧

中文机器翻译题面 查看原题
莲花-柑橘!
⠀

你是一名冒险家,为未来公司 RoboCorp 工作。您当前的技能级别是 $$$[1, n]$$$ 范围内的整数 $$$s$$$,但您不知道其确切值。您的目标是通过完成 RoboCorp 的任务来达到技能 $$$\geq n$$$,但每个任务都需要花费宝贵的机器人币。

您可以选择任何难度和任何正整数持续时间(以小时为单位)的任务。但是,成本取决于新任务的长度以及新任务的难度与最近任务的比较。

让 $$$x$$$ 为你最近任务的难度。如果您想执行难度为 $$$y$$$ 且持续时间为 $$$l$$$ 的新任务:

  • 如果这是您的第一个任务,或者 $$$y \leq x$$$,则成本为 $$$l$$$ 机器人币。
  • 如果 $$$y \gt x$$$,则成本为 $$$1000 + l$$$ 机器人币。

只有当你执行的任务的难度与你当前的技能完全匹配时,你的技能才会提高:

  • 如果$$$y = s$$$,那么你的技能就会提高$$$l$$$。
  • 否则,你的技能不会改变。

每次任务结束后,你仍然不知道自己的实际技能值。

你从 $$$10^6$$$ 机器人币开始。找到一个不超出您的预算并保证您的技能至少达到 $$$n$$$ 的策略(一系列任务),无论您最初的技能是什么。

输入

输入包含一行整数 $$$n$$$($$$n = 4$$$ 或 $$$n = 250\,000$$$)——目标技能等级(也就是说,到最后,你的技能必须是 $$$\geq n$$$)。

这个问题(包括示例)总共有 $$$2$$$ 测试。该示例的 $$$n = 4$$$,另一个测试的 $$$n = 250\,000$$$。

此问题不允许进行黑客攻击。

输出

在第一行中,打印一个整数 $$$k$$$ ($$$0 \leq k \leq 10^6$$$) — 您计划完成的任务数。

然后,打印 $$$k$$$ 行。第 $$$i$$$ 行必须包含两个整数 $$$y$$$ 和 $$$l$$$ ($$$1 \leq y, l \leq 10^6$$$) - 分别是第 $$$i$$$ 任务的难度和持续时间(以小时为单位)。

示例

输入
复制

4

输出
复制

4
1 4
3 1
2 1
3 1

注意

在示例中,您的目标技能是 $$$n = 4$$$。您可以使用以下策略:

  • 执行难度 $$$y = 1$$$ 且持续时间 $$$l = 4$$$ 的任务。这是您的第一个任务,因此您支付 $$$l = 4$$$ 机器人币。
  • 执行难度 $$$y = 3$$$ 且持续时间 $$$l = 1$$$ 的任务。上一个任务的难度为 $$$x = 1$$$,因此由于 $$$y \gt x$$$,您需要支付 $$$l + 1000 = 1001$$$ 机器人币。
  • 执行难度 $$$y = 2$$$ 且持续时间 $$$l = 1$$$ 的任务。现在 $$$x = 3$$$,并且由于 $$$y \leq x$$$,您支付 $$$l = 1$$$ 机器人币。
  • 执行难度 $$$y = 3$$$ 且持续时间 $$$l = 1$$$ 的任务。现在 $$$x = 2$$$,并且由于 $$$y \gt x$$$,您支付 $$$l + 1000 = 1001$$$ 机器人币。

您总共花费了 $$$2007$$$ 机器人币,这在您的 $$$10^6$$$-机器人币预算之内。

现在我们验证此策略始终有效:

  • 如果你的初始技能是$$$1$$$,那么在第一个任务之后它会变成$$$5$$$。
  • 如果你的初始技能是$$$2$$$,第三次任务后它会变成$$$3$$$,第四次任务之后它会变成$$$4$$$。
  • 如果你的初始技能是$$$3$$$,那么在第二个任务之后它会变成$$$4$$$。
  • 如果你的初始技能为 $$$4$$$,则它仍为 $$$4$$$。

所以无论你的起始技能是什么,你最终都会获得技能$$$\geq n$$$。