题目描述

有价值分别为 $1 \sim 6$ 的大理石各 $a[1] \sim a[6]$ 块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。

其中大理石的总数不超过 $20000$。

输入格式

输入包含多组数据！

每组数据占一行，包含 $6$ 个整数，表示 $a[1] \sim a[6]$。

当输入为 0 0 0 0 0 0 时表示输入结束，且该行无需考虑。

输出格式

每组数据输出一个结果，每个结果占一行。

如果可以实现则输出 Can，否则输出 Can't。

样例

4 7 4 5 9 1
9 8 1 7 2 4
6 6 8 5 9 2
1 6 6 1 0 7
5 9 3 8 8 4
0 0 0 0 0 0

Can't
Can
Can't
Can't
Can

样例解释

第一组数据

4 7 4 5 9 1
解释：有 4 块价值 1，7 块价值 2，4 块价值 3，5 块价值 4，9 块价值 5，1 块价值 6。
总价值 = $4 \times 1 + 7 \times 2 + 4 \times 3 + 5 \times 4 + 9 \times 5 + 1 \times 6 = 4 + 14 + 12 + 20 + 45 + 6 = 101$。
总和为奇数，不可能平分，输出 Can't。

第二组数据

9 8 1 7 2 4
总价值 = $9 \times 1 + 8 \times 2 + 1 \times 3 + 7 \times 4 + 2 \times 5 + 4 \times 6 = 9 + 16 + 3 + 28 + 10 + 24 = 90$。
总和为偶数，可以尝试划分。存在一种划分方式使两部分价值各为 45，输出 Can。

第三组数据

6 6 8 5 9 2
总价值 = $6 \times 1 + 6 \times 2 + 8 \times 3 + 5 \times 4 + 9 \times 5 + 2 \times 6 = 6 + 12 + 24 + 20 + 45 + 12 = 119$（奇数），输出 Can't。

第四组数据

1 6 6 1 0 7
总价值 = $1 \times 1 + 6 \times 2 + 6 \times 3 + 1 \times 4 + 0 \times 5 + 7 \times 6 = 1 + 12 + 18 + 4 + 0 + 42 = 77$（奇数），输出 Can't。

第五组数据

5 9 3 8 8 4
总价值 = $5 \times 1 + 9 \times 2 + 3 \times 3 + 8 \times 4 + 8 \times 5 + 4 \times 6 = 5 + 18 + 9 + 32 + 40 + 24 = 128$（偶数），可以平分，输出 Can。

数据范围

• 大理石总数不超过 20000，即 $\sum_{i=1}^6 a[i] \le 20000$。
• 价值为 $1 \sim 6$。

算法分析

这是一个多重背包可行性问题。

思路

设总价值为 $sum$，如果 $sum$ 为奇数，直接输出 Can't。

如果 $sum$ 为偶数，目标是从这些大理石中选出若干块，使得总价值为 $sum/2$。

每种价值的大理石有 $a[i]$ 块，可以转化为多重背包问题：
背包容量为 $sum/2$，有 $6$ 种物品，第 $i$ 种物品价值为 $i$，数量为 $a[i]$，问是否能恰好装满背包。

多重背包优化

由于大理石总数最多 20000，价值最大为 6，$sum/2$ 最大约为 $20000 \times 6 / 2 = 60000$。
直接多重背包 DP 复杂度为 $O(sum \times \sum a[i])$ 可能过大。

可以使用二进制优化将多重背包转化为 01 背包，或者使用可行性 DP 的特殊优化（单调队列优化或 bitset 优化）。

这里推荐使用 bitset 优化，因为状态只有“是否可达”，且 $sum/2$ 最大 60000，bitset 仅需约 60000 位，即约 7500 字节，非常高效。

算法步骤

1. 读入 $a[1] \dots a[6]$。
2. 如果全为 0，结束。
3. 计算总价值 $sum = \sum_{i=1}^6 i \times a[i]$。
4. 如果 $sum$ 为奇数，输出 Can't。
5. 否则，令 $target = sum / 2$。
6. 用 bitset 表示可达状态：bitset<60001> dp，dp[0] = 1。
7. 对每种价值 $i$（1 到 6），有 $a[i]$ 块，用二进制拆分或直接使用 bitset 移位加速：
   dp |= dp << i 重复 $a[i]$ 次，但这样太慢。可以二进制拆分：将 $a[i]$ 拆成 $1, 2, 4, \dots$ 等 2 的幂次份，每份作为一个物品做 01 背包。
8. 如果 dp[target] == 1，输出 Can，否则输出 Can't。

二进制拆分方法

对于数量 $a[i]$，将其拆分为 $2^0, 2^1, 2^2, \dots$ 直到剩余不足 $2^k$ 的部分作为最后一份。每份对应一个物品，价值 = 份数 $\times i$，体积 = 份数 $\times i$（本题中价值等于体积）。
然后用 01 背包方式更新 bitset。

复杂度分析

• 二进制拆分后物品总数为 $O(\sum \log a[i]) \le O(6 \times \log 20000) \approx 90$。
• bitset 更新复杂度为 $O(target / word\_size)$，word_size 通常为 64，所以很快。
• 可以通过本题。

提示

• 注意数组大小，$target$ 最大为 60000。
• 使用 bitset 需要包含 <bitset> 头文件。
• 每组数据重新初始化 bitset。