1506. [POJ 1014]Dividing

【题目描述】

$Marsha$ 和 $Bill$ 收藏了一些大理石。他们想要把这些大理石平均分配给两个人。如果大理石的价值一样，这将很容易做到，因为他们可以简单的对半分。不幸的是，一些大理石比其他的更大或者更漂亮。因此 $Marsha$ 和 $Bill$ 给每个大理石都规定了一个价值，它是一个 $1 \sim 6$ 之间的自然数。现在他们想要把这些大理石分成两部分，每部分的价值之和相等。但他们很快意识到有可能不存在这样的分法（即使大理石的价值之和是偶数）。 例如，如果有一颗价值为 $1$ 的大理石、一颗价值为 $3$ 的大理石和两颗价值为 $4$ 的大理石，那么这些大理石就无法分成等值的两组。因此，他们请你写一个程序，判断是否存在公平的分法。

【输入格式】

输入包含多组数据。

每组数据由 $1$ 行，包含 $6$ 个正整数 $n_1 \sim n_6$，其中 $n_i$ 是价值为 $i$ 的大理石数量。 因此题目描述中的例子可以被表示为 "$1\ 0\ 1\ 2\ 0\ 0$"。大理石的总数不超过 $20000$.

【输出格式】

对第 $k$ 组数据，输出一行"Collection #k:"，再输出一行"Can be divided."或"Can't be divided."，然后再输出一个空行。

【样例输入】

1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0

【样例输出】

Collection #1:
Can't be divided.

Collection #2:
Can be divided.

【来源】

Mid-Central European Regional Contest 1999

POJ 1014 Dividing