问题抽象

这是一个典型的完全背包问题（无界背包）的变体，或是纯粹的数学丢番图方程求解。

给定常数项集 ，求解满足方程 的非负整数解 ，并使得目标函数 取最小值。若无解，则输出 -1。

核心思想：极限贪心 + 最小公倍数剪枝（数学同余）

为了使总袋数最小，必须最大化使用 8 号袋的数量。 假设我们先全部使用 8 号袋，令初始 8 袋数为 ，余数为 。 余数 的取值仅可能为偶数：。此时存在严格的数学收敛规律：

  • 当 ：完美整除，需要的总袋数显然是 。
  • 当 ：恰好可以装满 1 个 6 号袋。总袋数为 。
  • 当 ：余数 4 无法装口袋。我们需要从已划分的 8 号袋中“退回”1 个袋子。退回后，余数为 。 恰好可以装满 2 个 6 号袋。总袋树变化量为：退回化 1 袋，增加 2 袋，净增加 1 袋。此时总袋数仍为 。
  • 当 ：需要退回 2 个 8 号袋。退回后，余数为 。 恰好装满 3 个 6 号袋。总袋数变化律为：退 2 进 3，净增加 1 袋。此时总袋数仍为 。

规律总结

对于任何能有效组合出的偶数，除了余数为 时结果为 之外，其余任意有余数的情况，满足条件的最小总袋数必定恒等于 。

我们只需排除那些“不够借位”的边缘无解偶数，即可在 复杂度下直接输出答案。无法提供足够“借位”的偶数分别为：

  • 余数为 4 时，需要至少 1 个 8 来借位，因此 无解。
  • 余数为 2 时，需要至少 2 个 8 来借位，因此 和 无解。

奇偶性与非法边界短路判定

判断输入变量 。如果满足以下任意一个条件，直接判定为无解，输出 -1：

  1. n % 2 != 0 （奇数，根本无法由 6 和 8 组合）
  2. n == 10 （偶数盲区，n/8=1 余 2，借无可借）
  3. n < 6 （数值过小，连最小的一袋都装不满。此处恰好包含前文推演的奇数边界以及特殊偶数边界 n=2 和 n=4）

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    if (n % 2 != 0 || n == 10 || n < 6) {
        cout << -1 << endl;
        return 0;
    }

    int k = n / 8;
    int r = n % 8;
    if (r == 0) {
        cout << k << endl;
    } else {
        cout << (k + 1) << endl;
    }
}