洛谷 P2036 PERKET

// 洛谷 P2036 PERKET —— 第 ① 版：忘了「至少选一种」（**这一版是错的**）
//
// 输入：第一行 n；接下来 n 行每行两个整数 s b（酸度、苦度）
// 输出：本该是「总酸度和总苦度」的最小绝对差
//
// 这份为什么存在：这道题就是第 3 章那棵**子集树**的原样搬运 ——
// 每种配料「选或不选」，走到底算一次差值。写起来太顺了，顺到会漏掉题面里的一句话：
//
//   「另外，我们必须添加**至少一种**配料，因为没有任何食物是只以水为配料的。」
//
// ⚠ 不选任何配料时：总酸度是**空乘积 = 1**，总苦度是**空和 = 0**，差值 = 1。
//    这个 1 常常比真正的答案还小，于是**每道数据的答案都被它压成 1**。
//
//    样例一（n = 1，配料 3 10）的正确答案是 7，这一版会给 **1**。
//
// ★★ 这一课值得单独记：**题面里那种「另外，…」「注意，…」开头的补充句，
//    往往就是唯一一个会挂人的约束。** 读题时看到它们，立刻在代码里找到对应的那一行。
//
// ⚠ 而且它藏得很好：样例三的正确答案**正好也是 1**，光看那一组根本发现不了。

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

int n;
int s[15], b[15];
int best = INT_MAX;

// 轮到第 i 种配料，当前总酸度 sour（乘积）、总苦度 bitter（和）
void dfs(int i, long long sour, long long bitter) {
    if (i == n) {
        best = min(best, (int)llabs(sour - bitter));   // ⚠ 一个都没选也被算进来了
        return;
    }
    dfs(i + 1, sour * s[i], bitter + b[i]);            // 选
    dfs(i + 1, sour, bitter);                          // 不选
}

int main() {
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> s[i] >> b[i];
    dfs(0, 1, 0);                                      // 酸度是乘积，初值 1；苦度是和，初值 0
    cout << best << "\n";
    return 0;
}

// 洛谷 P2036 PERKET —— 第 ② 版：数一数选了几种（正解）
//
// 输入：第一行 n（1 <= n <= 10）；接下来 n 行每行两个整数 s b
// 输出：总酸度和总苦度的最小绝对差
//
// 和第 ① 版的差别只有一处：**多带一个「已经选了几种」的计数，一种都没选就不参与比较**。
//
//     if (i == n) {
//         if (cnt > 0) best = min(best, ...);        // ★ 就是这个 cnt > 0
//         return;
//     }
//
// 这就是第 3 章那棵子集树，一个字都没变 —— 只是在出口那儿加了一道闸。
//
// ⚠ 为什么不干脆「先算全不选的，再排除掉」：因为 best 的初值一旦被那个 1 占住，
//   后面再也没机会更新回去。**闸门要设在数据进来的地方，不是出去的地方。**
//
// 数值范围：题面保证「全部使用产生的总酸度和总苦度小于 1e9」，int 够用；
// 这里仍然用 long long 存中间量 —— 乘积这种东西，多一层保险不花钱。

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

int n;
int s[15], b[15];
int best = INT_MAX;

// 轮到第 i 种配料；cnt 是已经选了几种；sour 是乘积，bitter 是和
void dfs(int i, int cnt, long long sour, long long bitter) {
    if (i == n) {
        if (cnt > 0) best = min(best, (int)llabs(sour - bitter));    // ★ 至少选一种
        return;
    }
    dfs(i + 1, cnt + 1, sour * s[i], bitter + b[i]);                 // 选
    dfs(i + 1, cnt, sour, bitter);                                   // 不选
}

int main() {
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> s[i] >> b[i];
    dfs(0, 0, 1, 0);
    cout << best << "\n";
    return 0;
}

// 洛谷 P2036 PERKET —— 第 ③ 版：n <= 10，直接二进制枚举（同样能过）
//
// 输入 / 输出：和第 ② 版完全一样
//
// 这份为什么存在：n 只有 10，子集一共 2^10 = 1024 个 —— **少到可以一个个数过去**。
// 于是连递归都不用：拿一个整数的二进制位表示「哪几种配料被选中」。
//
//     mask 的第 i 位是 1  <=>  选了第 i 种配料
//
// ★ 而「至少选一种」这个约束，在这种写法里变成了**循环的起点**：
//
//     for (int mask = 1; mask < (1 << n); mask++)
//                    ~~~
//                    从 1 开始，不是从 0 —— mask = 0 正好就是「一种都不选」
//
//   ⇒ 同一个约束，在递归写法里是一句 if，在二进制写法里是一个起点。
//     **换个表示法，约束可以变得更难忘记** —— 这一条第 3 章、第 4 章都讲过。
//
// ⚠ 但别倒过来理解成「二进制枚举更好」：它只在 n 很小（一般 n <= 20）时能用，
//   而且**它不让你站在决策过程的中间**，所以一旦需要剪枝就用不了了（第 3 章第 5 步讲过）。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<int> s(n), b(n);
    for (int i = 0; i < n; i++) cin >> s[i] >> b[i];

    int best = INT_MAX;
    for (int mask = 1; mask < (1 << n); mask++) {      // ★ 从 1 开始 = 至少选一种
        long long sour = 1, bitter = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) { sour *= s[i]; bitter += b[i]; }
        best = min(best, (int)llabs(sour - bitter));
    }

    cout << best << "\n";
    return 0;
}