洛谷 P1120 [CERC 1995] 小木棍

// P1120 的**第一版**：枚举原长 L，DFS 一根一根拼，**一条剪枝都不加**。
//
// 题目：n 根小木棍（长度 a[i] ≤ 50），它们是若干根**等长**的原始木棍砍出来的。
//       求原始木棍的**最小可能长度**。
//
// 它已经带着两条**几乎没人会漏**的东西：
//   ① 只枚举 `sum % L == 0` 的 L（拼出来的总长必须正好是 sum）；
//   ② `dfs(done, cur, start)` 里只从第 start 根往后挑 —— 同一根木棍里的几段
//      是一个**组合**不是排列，不这么写会把同一种拼法数很多遍。
//
// ⚠ 这一版**是对的**，它只是跑不完：题面顶格（n = 65）它会卡到天荒地老。
//   页面第 ④ 步用一张表量了「再加四条剪枝分别值多少钱」。

#include <bits/stdc++.h>
using namespace std;

static int n, a[70], L, need;
static bool used_[70];
static long long nodes = 0;                 // dfs 进了多少次 —— 这一页的尺子

static bool dfs(int done, int cur, int start) {
    nodes++;
    if (done == need) return true;
    if (cur == L) return dfs(done + 1, 0, 0);
    for (int i = start; i < n; i++) {
        if (used_[i] || cur + a[i] > L) continue;
        used_[i] = true;
        if (dfs(done, cur + a[i], i + 1)) return true;
        used_[i] = false;
    }
    return false;
}

int main(int argc, char** argv) {
    if (!(cin >> n)) return 0;
    int sum = 0, mx = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }

    for (L = mx; L <= sum; L++) {
        if (sum % L) continue;
        need = sum / L;
        memset(used_, 0, sizeof used_);
        if (dfs(0, 0, 0)) break;
    }
    cout << L << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P1120 第二版：在第一版之上**只加一条** —— 木棍**从大到小排序**（剪枝 A）。
//
// 题目：n 根小木棍（长度 a[i] ≤ 50），它们是若干根**等长**的原始木棍砍出来的。
//       求原始木棍的**最小可能长度**。
//
// ★ 为什么先放大的：大木棍能放的位置少、约束强，**早点撞墙就早点回头**。
//   而且配合「只从第 start 根往后挑」，排完序之后长度相同的木棍是挨着的 ——
//   下一版那条剪枝（跳过和刚失败的等长木棍）**要靠这一条才成立**。
//   ⇒ 这是这一页第一处「两条剪枝互相搭台」的地方。

#include <bits/stdc++.h>
using namespace std;

static int n, a[70], L, need;
static bool used_[70];
static long long nodes = 0;                 // dfs 进了多少次 —— 这一页的尺子

static bool dfs(int done, int cur, int start) {
    nodes++;
    if (done == need) return true;
    if (cur == L) return dfs(done + 1, 0, 0);
    for (int i = start; i < n; i++) {
        if (used_[i] || cur + a[i] > L) continue;
        used_[i] = true;
        if (dfs(done, cur + a[i], i + 1)) return true;
        used_[i] = false;
    }
    return false;
}

int main(int argc, char** argv) {
    if (!(cin >> n)) return 0;
    int sum = 0, mx = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }
    sort(a, a + n, greater<int>());          // A：从大到小

    for (L = mx; L <= sum; L++) {
        if (sum % L) continue;
        need = sum / L;
        memset(used_, 0, sizeof used_);
        if (dfs(0, 0, 0)) break;
    }
    cout << L << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P1120 第三版：排序之上**再加一条** —— 跳过和「刚失败的那根」等长的木棍（剪枝 B）。
//
// 题目：n 根小木棍（长度 a[i] ≤ 50），它们是若干根**等长**的原始木棍砍出来的。
//       求原始木棍的**最小可能长度**。
//
// 道理：刚拿一根长度 5 的放进去、往下走失败了，那么**再拿另一根长度 5 的放进去，
//   接下来面对的局面一模一样**（剩下能用的木棍是同一个多重集合），必然也失败。
//
// ⚠⚠ 而它有一个**很容易写错的写法**：写成「和上一根等长就跳过」（`a[i] == a[i-1]`）——
//   那是无条件跳过，会把「这一层第一次用这个长度」也一起跳掉，**剪过头**。
//   那一版见 p1120Wrong.cpp，页面第 ⑥ 步专门对拍抓它。
//   ⇒ 判据是「上一次**失败**的长度」，不是「上一根的长度」。

#include <bits/stdc++.h>
using namespace std;

static int n, a[70], L, need;
static bool used_[70];
static long long nodes = 0;                 // dfs 进了多少次 —— 这一页的尺子

static bool dfs(int done, int cur, int start) {
    nodes++;
    if (done == need) return true;
    if (cur == L) return dfs(done + 1, 0, 0);
    int fail = 0;                           // B：上一次在这一层失败的长度
    for (int i = start; i < n; i++) {
        if (used_[i] || a[i] == fail || cur + a[i] > L) continue;
        used_[i] = true;
        if (dfs(done, cur + a[i], i + 1)) return true;
        used_[i] = false;
        fail = a[i];
    }
    return false;
}

int main(int argc, char** argv) {
    if (!(cin >> n)) return 0;
    int sum = 0, mx = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }
    sort(a, a + n, greater<int>());          // A：从大到小

    for (L = mx; L <= sum; L++) {
        if (sum % L) continue;
        need = sum / L;
        memset(used_, 0, sizeof used_);
        if (dfs(0, 0, 0)) break;
    }
    cout << L << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P1120 小木棍 —— 枚举原长 ＋ 四层剪枝的 DFS（★ 这一版就能 AC）
//
// 题目：n 根小木棍（长度 a[i] ≤ 50），它们是若干根**等长**的原始木棍砍出来的。
//       求原始木棍的**最小可能长度**。
//
// 框架只有两层：
//   ① 从小到大枚举原长 L —— 第一个拼得出来的 L 就是答案；
//      ⚠ 只有 `sum % L == 0` 的 L 才可能（拼出来的总长必须正好是 sum）。
//      ★ 而且**不能二分** —— 可行性对 L 不单调，页面第 ② 步有一组三根木棍的反例。
//   ② 对固定的 L，DFS 一根一根拼：`dfs(done, cur, start)`
//      = 已经拼好 done 根、当前这根拼到 cur 长、只允许再从第 start 根往后挑。
//
// ★★★ 而这道题的分数**全部**来自下面四条剪枝（页面第 ④ 步一条一条量了它们值多少钱）：
//   A 从大到小排序          —— 大的先放，早点撞墙
//   B 跳过和「刚失败的那根」等长的木棍
//   C ⚠ `cur == 0` 就失败 ⇒ **整个 L 都不可能**，直接返回
//   D ⚠ 正好补满（`cur + a[i] == L`）还失败 ⇒ 也直接返回
//
//   C 和 D 是两句反证：这根木棍的第一段随便挑一根都拼不成 ⇒ 换谁当第一段都一样；
//   而「正好补满」是最理想的收尾，它都不行 ⇒ 别的收法更不行。

#include <bits/stdc++.h>
using namespace std;

static int n, a[70], L, need;
static bool used_[70];
static long long nodes = 0;                 // dfs 进了多少次 —— 这一页的尺子

static bool dfs(int done, int cur, int start) {
    nodes++;
    if (done == need) return true;
    if (cur == L) return dfs(done + 1, 0, 0);
    int fail = 0;                           // B：上一次在这一层失败的长度
    for (int i = start; i < n; i++) {
        if (used_[i] || a[i] == fail || cur + a[i] > L) continue;
        used_[i] = true;
        if (dfs(done, cur + a[i], i + 1)) return true;
        used_[i] = false;
        fail = a[i];
        if (cur == 0 || cur + a[i] == L) return false;   // C / D
    }
    return false;
}

int main(int argc, char** argv) {
    if (!(cin >> n)) return 0;
    int sum = 0, mx = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }
    sort(a, a + n, greater<int>());          // A

    for (L = mx; L <= sum; L++) {
        if (sum % L) continue;
        need = sum / L;
        memset(used_, 0, sizeof used_);
        if (dfs(0, 0, 0)) break;
    }
    cout << L << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P1120 的**错法：剪过头**。和 p1120.cpp 只差一个字 —— `fail` 忘了写在函数里面。
//
// 题目：n 根小木棍（长度 a[i] ≤ 50），它们是若干根**等长**的原始木棍砍出来的。
//       求原始木棍的**最小可能长度**。
//
// ★★★ 本章第 8 步说过：剪枝写错**多半不是漏剪，是剪过头** —— 程序照样跑得飞快，
//   只是答案偏大（因为它把通向正确解的那条分支剪掉了）。这一版就是那样。
//
// 差别只有一行：`int fail` 从「dfs 里的局部变量」变成了**全局变量**。
//   于是「上一次失败的长度」不再属于**这一层**，而是被所有层共用 ——
//   在深处失败留下的 fail，会一路污染回上层，让上层跳过本来该试的木棍。
//
// ⚠⚠ 而它**照样过官方样例**（页面第 ⑥ 步），只有对拍抓得到。
//
// 框架只有两层：
//   ① 从小到大枚举原长 L —— 第一个拼得出来的 L 就是答案；
//      ⚠ 只有 `sum % L == 0` 的 L 才可能（拼出来的总长必须正好是 sum）。
//      ★ 而且**不能二分** —— 可行性对 L 不单调，页面第 ② 步有一组三根木棍的反例。
//   ② 对固定的 L，DFS 一根一根拼：`dfs(done, cur, start)`
//      = 已经拼好 done 根、当前这根拼到 cur 长、只允许再从第 start 根往后挑。
//
// ★★★ 而这道题的分数**全部**来自下面四条剪枝（页面第 ④ 步一条一条量了它们值多少钱）：
//   A 从大到小排序          —— 大的先放，早点撞墙
//   B 跳过和「刚失败的那根」等长的木棍
//   C ⚠ `cur == 0` 就失败 ⇒ **整个 L 都不可能**，直接返回
//   D ⚠ 正好补满（`cur + a[i] == L`）还失败 ⇒ 也直接返回
//
//   C 和 D 是两句反证：这根木棍的第一段随便挑一根都拼不成 ⇒ 换谁当第一段都一样；
//   而「正好补满」是最理想的收尾，它都不行 ⇒ 别的收法更不行。

#include <bits/stdc++.h>
using namespace std;

static int n, a[70], L, need;
static bool used_[70];
static long long nodes = 0;                 // dfs 进了多少次 —— 这一页的尺子
static int fail = 0;                        // ★ 错在这里：它该是 dfs 里的局部变量

static bool dfs(int done, int cur, int start) {
    nodes++;
    if (done == need) return true;
    if (cur == L) return dfs(done + 1, 0, 0);
    for (int i = start; i < n; i++) {
        if (used_[i] || a[i] == fail || cur + a[i] > L) continue;
        used_[i] = true;
        if (dfs(done, cur + a[i], i + 1)) return true;
        used_[i] = false;
        fail = a[i];
        if (cur == 0 || cur + a[i] == L) return false;   // C / D
    }
    return false;
}

int main(int argc, char** argv) {
    if (!(cin >> n)) return 0;
    int sum = 0, mx = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }
    sort(a, a + n, greater<int>());          // A

    for (L = mx; L <= sum; L++) {
        if (sum % L) continue;
        need = sum / L;
        memset(used_, 0, sizeof used_);
        if (dfs(0, 0, 0)) break;
    }
    cout << L << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P1120 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1120Count`      人看的版本
// `./p1120Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 六段：
//   ① 官方样例：答案 ＋ dfs 节点数；
//   ② ★ 软数据（砍碎生成器 40 组）上，四条剪枝 A/B/C/D 的 **16 种开关组合**各走多少节点；
//   ③ ★★★ 硬数据（顶格随机 40 组，n = 65、长度 1~50）上的同一张表 ——
//      ⚠ 这里得给节点数设上限，不然一条剪枝都不加的那几档根本不返回；
//      于是多出一把尺子：**「撞上限」的组数**（比节点数合计更抗上限的选择）。
//   ④ ★★★ 「几条剪枝合起来值多少」—— 是相加？是相乘？两档数据给出**相反方向**的答案。
//   ⑤ ★★★ 长尾：顶格随机 200 组，中位数只有几十个节点，可最难的那几组几百万也出不来。
//      ⇒ 题面开头那句「不保证存在可以通过任意符合要求的输入数据的程序」不是客套话。
//   ⑥ ★★★ 「fail 写成全局」那个剪过头的错法 —— 它在两档数据上的**后果完全不同**：
//      砍碎档是「答案偏大」，顶格随机档是「**跑不完**」（它把正确的 L 剪掉了，
//      于是一路往上试更大的 L，而那些 L 的搜索树大得多）。
//      ＋ 一组三根木棍的反例（可行性对 L 不单调 ⇒ 不能二分）。

#include <bits/stdc++.h>
using namespace std;

static bool CSV = false;
static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

/* ─────────── 一份参数化的搜索：A 排序 / B 跳等长 / C 首段失败 / D 补满失败 ─────────── */
struct Solver {
    int n = 0, L = 0, need = 0;
    vector<int> a;
    vector<char> used;
    bool A = true, B = true, C = true, D = true, globalFail = false;
    long long nodes = 0, cap = 0;
    int gfail = 0;
    int lastL = 0;                           // 撞上限时正在试的那个 L

    bool dfs(int done, int cur, int start) {
        if (cap && nodes >= cap) return false;
        nodes++;
        if (done == need) return true;
        if (cur == L) return dfs(done + 1, 0, 0);
        int localFail = 0;
        int& fail = globalFail ? gfail : localFail;
        for (int i = start; i < n; i++) {
            if (used[i] || cur + a[i] > L) continue;
            if (B && a[i] == fail) continue;
            used[i] = true;
            if (dfs(done, cur + a[i], i + 1)) return true;
            used[i] = false;
            if (cap && nodes >= cap) return false;
            fail = a[i];
            if ((C && cur == 0) || (D && cur + a[i] == L)) return false;
        }
        return false;
    }

    /** 返回答案；撞上节点上限返回 -1。 */
    int run(const vector<int>& in) {
        a = in;
        n = (int)a.size();
        nodes = 0; gfail = 0;
        if (A) sort(a.begin(), a.end(), greater<int>());
        int sum = 0, mx = 0;
        for (int x : a) { sum += x; mx = max(mx, x); }
        for (L = mx; L <= sum; L++) {
            if (sum % L) continue;
            need = sum / L;
            used.assign(n, 0);
            if (dfs(0, 0, 0)) return L;
            if (cap && nodes >= cap) { lastL = L; return -1; }
        }
        return sum;
    }
};

static int lastCapL = 0;                     // 上一次撞上限时正在试的 L
static int solveWith(const vector<int>& in, bool A, bool B, bool C, bool D,
                     long long& nodes, long long cap = 0, bool gf = false) {
    Solver s;
    s.A = A; s.B = B; s.C = C; s.D = D; s.cap = cap; s.globalFail = gf;
    int r = s.run(in);
    nodes = s.nodes;
    lastCapL = s.lastL;
    return r;
}

/* ─────────── 生成器（和 p1120Gen.cpp 逐字一致） ─────────── */
static vector<int> gen(int seed, int mode, int p1, int p2) {
    mt19937 rng((unsigned)seed * 2654435761u + 12345u);
    vector<int> a;
    if (mode == 1) {
        int n = p1 > 0 ? p1 : 65, hi = p2 > 0 ? p2 : 50;
        n = max(1, min(65, n));
        hi = max(1, min(50, hi));
        for (int i = 0; i < n; i++) a.push_back((int)(rng() % hi) + 1);
    } else {
        int L = p1 > 0 ? p1 : (int)(rng() % 33 + 8);
        int k = p2 > 0 ? p2 : (int)(rng() % 4 + 2);
        L = max(1, min(50, L));
        for (int t = 0; t < k; t++) {
            int rest = L;
            while (rest > 0) { int piece = (int)(rng() % rest) + 1; a.push_back(piece); rest -= piece; }
        }
        while ((int)a.size() > 65) {
            int cut = 0, sum = 0;
            for (int i = 0; i < (int)a.size(); i++) { sum += a[i]; if (sum == L) { cut = i + 1; break; } }
            if (!cut) break;
            a.erase(a.begin(), a.begin() + cut);
        }
        shuffle(a.begin(), a.end(), rng);
    }
    return a;
}

/** 跑一张 16 组合表；cap = 0 表示不设上限。返回节点数合计和「撞上限」组数。 */
static void comboTable(const vector<vector<int>>& data, long long cap,
                       long long tot[16], long long over[16]) {
    for (int m = 0; m < 16; m++) {
        tot[m] = over[m] = 0;
        for (const auto& in : data) {
            long long nd;
            int r = solveWith(in, m & 1, m & 2, m & 4, m & 8, nd, cap);
            tot[m] += nd;
            if (r < 0) over[m]++;
        }
    }
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");
    const vector<int> SAMPLE = {5, 2, 1, 5, 2, 1, 5, 2, 1};
    const char* NAME[4] = {"A 排序", "B 跳等长", "C 首段失败", "D 补满失败"};

    /* ① 官方样例 */
    {
        long long na, ns;
        int ans = solveWith(SAMPLE, true, true, true, true, na);
        int slow = solveWith(SAMPLE, false, false, false, false, ns);
        if (!CSV) printf("① 官方样例：正解 %d（%lld 个节点）／ 一条剪枝都不加 %d（%lld 个节点）\n",
                         ans, na, slow, ns);
        row("sample", {ans, na, slow, ns});
    }

    const int ROUNDS = 40;
    long long softTot[16], softOver[16], hardTot[16], hardOver[16];

    /* ② 软数据：砍碎生成器 */
    {
        vector<vector<int>> data;
        for (int s = 1; s <= ROUNDS; s++) data.push_back(gen(s, 0, 0, 0));
        comboTable(data, 0, softTot, softOver);
        if (!CSV) {
            printf("\n② 软数据（砍碎生成器 %d 组）：16 种剪枝组合的节点数合计\n", ROUNDS);
            for (int m = 0; m < 16; m++)
                printf("  A=%d B=%d C=%d D=%d  %lld\n", m & 1, (m >> 1) & 1, (m >> 2) & 1, (m >> 3) & 1, softTot[m]);
        }
        row("soft", vector<long long>(softTot, softTot + 16));
    }

    /* ③ 硬数据：顶格随机（n = 65、长度 1~50），节点上限 20 万 */
    const long long CAP = 200000;
    {
        vector<vector<int>> data;
        for (int s = 1; s <= ROUNDS; s++) data.push_back(gen(s, 1, 65, 50));
        comboTable(data, CAP, hardTot, hardOver);
        if (!CSV) {
            printf("\n③ 硬数据（顶格随机 %d 组，n = 65、长度 1~50；节点上限 %lld）\n", ROUNDS, CAP);
            for (int m = 0; m < 16; m++)
                printf("  A=%d B=%d C=%d D=%d  节点 %-10lld 撞上限 %lld 组\n",
                       m & 1, (m >> 1) & 1, (m >> 2) & 1, (m >> 3) & 1, hardTot[m], hardOver[m]);
        }
        row("hard", vector<long long>(hardTot, hardTot + 16));
        row("hardOver", vector<long long>(hardOver, hardOver + 16));
    }

    /* ④ ★★★ 相加？相乘？两档数据给出相反的方向 */
    if (!CSV) {
        printf("\n④ 每一条单独开 vs 四条一起开（万分比，越小越好）\n");
        for (int t = 0; t < 2; t++) {
            const long long* T = t ? hardTot : softTot;
            printf("  %s：\n", t ? "硬数据" : "软数据");
            double prod = 1;
            for (int i = 0; i < 4; i++) {
                int m = 1 << i;
                double r = T[m] * 1.0 / T[0];
                prod *= r;
                printf("    只开 %-10s %lld（%.4f 倍）\n", NAME[i], T[m], r);
            }
            printf("    四条一起开 %lld（%.4f 倍）；四个单独倍数**相乘**是 %.4f —— %s\n",
                   T[15], T[15] * 1.0 / T[0], prod,
                   T[15] * 1.0 / T[0] < prod ? "实测比相乘还好（互相搭台）" : "实测比相乘差（互相吃掉）");
        }
    }

    /* ⑤ ★★★ 长尾：顶格随机 200 组的分布 */
    {
        const int R = 200;
        const long long TAIL_CAP = 1000000;
        if (!CSV) printf("\n⑤ 长尾：顶格随机 %d 组，正解的节点数分布（上限 %lld）\n", R, TAIL_CAP);
        vector<long long> out;
        const int HI[3] = {50, 50, 15};
        const int NN[3] = {65, 30, 65};
        for (int t = 0; t < 3; t++) {
            vector<long long> all;
            int over = 0;
            for (int s = 1; s <= R; s++) {
                long long nd;
                if (solveWith(gen(s, 1, NN[t], HI[t]), true, true, true, true, nd, TAIL_CAP) < 0) over++;
                all.push_back(nd);
            }
            sort(all.begin(), all.end());
            out.push_back(all[R / 2]);
            out.push_back(over);
            if (!CSV) printf("  n = %2d、长度 1~%2d：中位数 %lld 个节点，撞上限的有 %d / %d 组\n",
                             NN[t], HI[t], all[R / 2], over, R);
        }
        row("tail", out);
    }

    /* ⑥ 「fail 写成全局」的错法 ＋ 不单调反例 */
    {
        if (!CSV) printf("\n⑥ 「fail 写成全局」那个剪过头的错法（每档 300 轮）\n");
        vector<long long> got;
        // 砍碎档（默认 / 短原长 / 多根） + 顶格随机档
        const int P[4][4] = {{0, 0, 0, 0}, {0, 12, 3, 0}, {0, 20, 6, 0}, {1, 65, 50, 0}};
        // ⚠⚠ 这一段有一个坑，第一版就踩了：顶格随机那一档里**有一边会跑不完**，
        //   所以必须给它上限，并且**分清楚是谁跑不完** ——
        //   第一版把「正解超时 = -1、错法给了个数」也记成一次「抓到」，量出来 171，全是假的。
        //   ⇒ 三个数分开报：答案真的不同的轮数 ／ 错法撞上限的轮数 ／ 正解撞上限的轮数。
        for (auto& p : P) {
            int bad = 0, badSlow = 0, refSlow = 0, past = 0, stuck = 0;
            for (int s = 1; s <= 300; s++) {
                vector<int> in = gen(s, p[0], p[1], p[2]);
                long long n1, n2;
                int r1 = solveWith(in, true, true, true, true, n1, 2000000);
                int r2 = solveWith(in, true, true, true, true, n2, 2000000, true);
                if (r1 < 0) refSlow++;
                if (r2 < 0) {
                    badSlow++;
                    // ★★★ 机制不能推，要量：它撞上限时正在试的是哪个 L？
                    //   草稿猜的是「它把正确的 L 剪掉了，跑到更大的 L 上白搜」—— 实测**不是**。
                    //   它绝大多数时候**就卡在正确答案那个 L 上**：解被剪掉了，找不到，
                    //   于是只能把这个 L 的整棵树穷举完才肯罢休 —— 而「证明无解」比「找到一个解」贵得多。
                    if (r1 >= 0 && lastCapL > r1) past++;
                    if (r1 >= 0 && lastCapL == r1) stuck++;
                }
                if (r1 >= 0 && r2 >= 0 && r1 != r2) bad++;
            }
            got.push_back(bad);
            got.push_back(badSlow);
            got.push_back(refSlow);
            got.push_back(past);
            got.push_back(stuck);
            if (!CSV) printf("  mode %d p=(%d,%d)：答案不同 %d 轮｜★ 错法自己撞上限 %d 轮"
                             "（卡在正确答案那个 L 上的 %d 轮，已经跑到更大的 L 上的 %d 轮）"
                             "｜正解撞上限 %d 轮（共 300）\n",
                             p[0], p[1], p[2], bad, badSlow, stuck, past, refSlow);
        }
        row("wrongCatch", got);

        vector<int> three = {2, 2, 2};
        vector<long long> mono;
        for (int L : {2, 3, 6}) {
            Solver s;
            s.a = three; s.n = 3; s.L = L; s.need = 6 / L; s.used.assign(3, 0);
            mono.push_back(s.dfs(0, 0, 0) ? 1 : 0);
        }
        if (!CSV) printf("\n★ 三根长度 2 的木棍（sum = 6）：L = 2 / 3 / 6 拼不拼得出 → %lld / %lld / %lld"
                         "（⇒ 可行性对 L 不单调，不能二分）\n", mono[0], mono[1], mono[2]);
        row("monotone", mono);
    }
    return 0;
}

// P1120 对拍生成器：`./p1120Gen <seed> [mode] [p1] [p2]`
//
//   mode 0（默认）**砍碎**：造 p1 长的原始木棍 p2 根，每根随机砍碎，打乱输出。
//                          ⇒ 一定拼得回去，答案 ≤ p1。（p1 / p2 留空则由 seed 决定）
//   mode 1        **顶格随机**：直接random 出 p1 根长度在 1 ~ p2 之间的木棍。
//                          ⇒ 这就是题面允许的最一般的输入（n ≤ 65、a ≤ 50）。
//
// ★★★ 这两档必须都跑，而它们量出来的东西完全不同（页面第 ⑤ ⑥ 步）：
//   mode 0 造出来的局面**几乎都是软的** —— 砍碎的段天然凑得回整根，
//     一条剪枝都不加也能很快跑完。它适合数「每条剪枝值多少钱」这种干净的倍数。
//   mode 1 才碰得到这道题真正的样子：**中位数只有几十个节点，可长尾极长** ——
//     300 组里有几组跑几百万个节点还出不来。
//
// ⚠ 而 mode 0 **不能自带答案**：砍碎之后可能存在比 p1 更小的原长
//   （极端情况全砍成 1，答案就是 1）。⇒ 对拍的参照物只能是另一份程序。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937 rng(seed * 2654435761u + 12345u);
    vector<int> a;

    if (mode == 1) {
        int n = argc > 3 ? atoi(argv[3]) : 65;
        int hi = argc > 4 ? atoi(argv[4]) : 50;
        n = max(1, min(65, n));
        hi = max(1, min(50, hi));
        for (int i = 0; i < n; i++) a.push_back((int)(rng() % hi) + 1);
    } else {
        int L = argc > 3 ? atoi(argv[3]) : 0;
        int k = argc > 4 ? atoi(argv[4]) : 0;
        if (L <= 0) L = (int)(rng() % 33 + 8);
        if (k <= 0) k = (int)(rng() % 4 + 2);
        L = max(1, min(50, L));
        for (int t = 0; t < k; t++) {
            int rest = L;
            while (rest > 0) {
                int piece = (int)(rng() % rest) + 1;
                a.push_back(piece);
                rest -= piece;
            }
        }
        // ⚠ 题面保证 n ≤ 65：砍得太碎就整根整根地丢，剩下的仍然拼得回去
        while ((int)a.size() > 65) {
            int cut = 0, sum = 0;
            for (int i = 0; i < (int)a.size(); i++) { sum += a[i]; if (sum == L) { cut = i + 1; break; } }
            if (!cut) break;
            a.erase(a.begin(), a.begin() + cut);
        }
        shuffle(a.begin(), a.end(), rng);
    }

    printf("%d\n", (int)a.size());
    for (size_t i = 0; i < a.size(); i++) printf("%d%c", a[i], i + 1 == a.size() ? '\n' : ' ');
    return 0;
}