本文最后更新于 7 个月前，文中所描述的信息可能已发生改变。

G. Git Gud 解题思路 ​

核心问题分析 ​

题目的设定非常像一个肉鸽（Roguelike）游戏的升级机制： 你的初始技能是 $[1, n]$ 中的一个未知数。你每次可以接一个难度为 $y$、耗时为 $l$ 的任务。

• 升级条件： 只有当任务难度 $y$ 恰好等于你当前的技能 $s$ 时，你的技能才会提升 $l$（变成 $s + l$）。否则无事发生。
• 扣费机制： 你的总预算是 $10^6$。如果你接的任务难度比上一个任务高（$y > x_{prev}$），除了耗时 $l$，还要额外扣除 $1000$ 块的“越级惩罚”。如果难度不高于上一个任务（$y \le x_{prev}$），则只需支付 $l$。

我们需要构造一个任务序列，使得不管初始技能是多少，最后必定能 $\ge n$（本题中 $n$ 最大为 $250000$）。

1. 破题：如何保证必定升级？（链式反应） ​

因为我们不知道自己初始的技能是多少，所以最稳妥的办法就是把所有可能的技能等级都“安排”一次任务。 假设对于每个等级 $x$，我们都设定一个步长 $l_x$，即安排一个难度为 $x$，耗时为 $l_x$ 的任务。如果恰好命中了，技能就会升级到 $next[x] = x + l_x$。

为了保证技能一路飙升到 $\ge n$，我们安排的任务顺序必须满足一个严苛的拓扑条件： 对于任意 $x$，难度为 $x$ 的任务，必须排在难度为 $next[x]$ 的任务的“前面”！ 这样才能形成“连击”：等级 $x \rightarrow$ 命中任务 $x$ 升到 $next[x] \rightarrow$ 后面又遇到任务 $next[x]$ 升到 $next[next[x]] \rightarrow \dots \ge n$。

设 $dist[x]$ 表示从 $x$ 升级到 $\ge n$ 所需要的步数（跳跃次数）。显然，$dist[x] = dist[next[x]] + 1$。 按照上面的逻辑，我们只需要按照 $dist$ 从大到小的层级去安排任务，就能完美满足这个拓扑序（因为 $dist[x]$ 必定大于 $dist[next[x]]$，所以 $x$ 会比 $next[x]$ 先执行）。

2. 预算危机：为什么需要分块？ ​

假设我们最简单粗暴地让每次升级只升 $1$ 级（即 $next[x] = x + 1$）。 那么 $dist$ 最大的层数会有 $250000$ 层。 按照 $dist$ 从大到小安排任务，意味着我们要先安排 $x=1$，然后安排 $x=2 \dots$ 依次递增。 这就出大问题了！因为难度 $y$ 一直在增加，每一次任务都会触发“越级惩罚”！ 总惩罚高达 $250000 \times 1000 = 2.5 \times 10^8$，远远超出了 $10^6$ 的预算。

我们需要一种能够在同一层级内从大到小安排任务（避免惩罚），同时层数又尽可能少（减少切换层级的惩罚）的策略。

顿悟时刻：多级跳表（分块）思想！ 我们可以把 $x$ 的步长分为三个档次：

• 大步长 $B_2$： 如果 $x$ 是 $B_2$ 的倍数，直接飞跃 $B_2$ 的距离。
• 中步长 $B_1$： 如果 $x$ 是 $B_1$ 的倍数，跨越 $B_1$ 的距离。
• 小步长 $1$： 普通的 $x$ 只能走 $1$ 步。

这实际上是构建了一棵 $3$ 层深度的树！ 为了让最大层数（max_d）最小化，我们取立方根：$\sqrt[3]{250000} \approx 63$。 所以我们设 $B_1 = 63$，$B_2 = 63 \times 63 = 3969$。 在这样的设定下，任何一个数字跑到 $n$，最多只需要： 走 $62$ 个小步到达 $B_1$ 的倍数 + 走 $62$ 个中步到达 $B_2$ 的倍数 + 走 $63$ 个大步到达终点。 总最大层数 max_d $\le 62 + 62 + 63 = 187$！

3. 完美构造：规避惩罚的极致贪心 ​

有了上面的结构，我们构造最终任务序列的逻辑如下：

1. 外层循环：按照层数 $d$ 从大到小遍历（即先处理离终点远的）。这满足了拓扑序，保证了必定升级。
2. 内层循环：在同一个层数 $d$ 内部，包含着许多不同的 $x$。我们把这些 $x$ 从大到小排列！ 因为从大到小执行，难度 $y$ 是递减的，完全符合 $y \le x_{prev}$ 的免罚条件，只需支付基础耗时 $l$。

只有在切换层数（从层 $d$ 换到层 $d-1$）时，难度 $y$ 可能会突然变大，触发一次 $1000$ 的惩罚。 但由于总层数 max_d 只有 $187$，所以惩罚总额最多为 $187 \times 1000 = 187,000$！ 再加上所有任务的基础耗时之和大约为 $250000$，总花费在 $430,000$ 左右，完美控制在 $10^6$ 的预算之内！

CPP 代码实现 ​

// G. Git Gud

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define sz(x) (int)x.size()
#define endl "\n"

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    // 为了覆盖所有测试用例，统一将目标放大到极限值 250000
    // 反正超过目标也是合法的
    n = 250000;
    
    // 分块大小：取 250000 的立方根附近的值
    int B1 = 63;
    int B2 = 3969; // 63 * 63
    
    vector<int> next(n + 1), dist(n + 1, 0);
    
    // 逆推每个节点的 next 去向和距终点的步数 dist
    for (int x = n - 1; x >= 1; x--) {
        if (x % B2 == 0) {
            next[x] = min(n, x + B2); // 大步跃进
        } else if (x % B1 == 0) {
            next[x] = min(n, x + B1); // 中步跨越
        } else {
            next[x] = min(n, x + 1);  // 小步挪动
        }
        // 当前点的距离 = 下一个点的距离 + 1
        dist[x] = dist[next[x]] + 1;
    }

    // 找出全图所需的最大步数（层数）
    int max_d = 0;
    for (int x = 1; x < n; x++) {
        max_d = max(max_d, dist[x]);
    }

    // lay[d] 存储距离终点恰好为 d 的所有技能节点 x
    vector<vector<int>> lay(max_d + 1);
    for (int x = 1; x < n; x++) {
        lay[dist[x]].push_back(x);
    }
    
    vector<pair<int, int>> ans;
    
    // 按照距离从远到近（从大到小）遍历，保证拓扑升级链
    for (int d = max_d; d >= 1; d--) {
        // 在同一层内，x 从大到小遍历
        // 这样难度是递减的，可以白嫖不用交 1000 的越级惩罚款
        for (int i = sz(lay[d]) - 1; i >= 0; i--) {
            int x = lay[d][i];
            // 压入答案序列：难度为 x，耗时为 next[x] - x
            ans.pb({x, next[x] - x});
        }
    }

    // 输出总任务数
    cout << sz(ans) << endl;
    
    // 输出具体的任务序列
    for (auto p : ans) {
        cout << p.first << ' ' << p.second << endl;
    }
}

signed main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t; // 本题仅单组数据

    while (t--) {
        solve();
    }
}