P13232 [GCJ 2015 #3] River Flow

你所在的城市坐落在壮观的二进制河（Binary river）岸边。河水来自高山上的一些支流。不幸的是，山上的农民需要用这些支流的水来灌溉庄稼。 很久以前，城市与农民达成了一项协议，允许他们在保证河水流动的同时进行耕作：每位农民被允许在一半的时间里为庄稼用水。农民们轮流用一天水，然后让水流入河一天。结果却是一场灾难！因为所有农民的用水时间是同步的，要么全部用水，要么全部不取水，导致河流每隔一天就会干涸，接着第二天又会泛滥。 为了解决这个问题，城市再次与农民协商，让每位农民选择一个介于 $1$ 到 $\mathbf{D}$（包含）之间的 $2$ 的整数次幂（毕竟这是二进制河），并且每经过该天数就切换一次用水状态（即开始或停止取水）。（并不是每个 $1$ 到 $\mathbf{D}$ 之间的 $2$ 的幂都一定被选择，多个农民可以选择相同的数字。$1$ 也算作 $2$ 的幂。）这样做的目的是让整体用水更加均匀，从而减少干旱和洪水的发生。 这一切都发生在很久以前，而你和其他市民最近开始怀疑农民们并没有遵守协议。（你甚至不知道现在有多少农民！）然而，你们唯一掌握的数据是 $\mathbf{N}$ 天的河流水量历史记录。你能判断农民们是否诚实吗？ 每条支流的流量为 $1$，主河道的流量等于所有未被农民取水的支流流量之和。（在查看记录之前，你并不知道有多少条支流。）每条支流最多只会被一位农民取水，也可能有些支流从未被农民取水。注意，农民们在城市开始记录水流之前就已经开始了他们的用水周期，但并不能保证他们都是在同一天开始的。

输入的第一行是测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行包含两个用空格分隔的整数 $\mathbf{N}$ 和 $\mathbf{D}$。下一行包含 $\mathbf{N}$ 个用空格分隔的整数，第 $\mathrm{i}$ 个整数 $\mathbf{d}_{\mathrm{i}}$ 表示第 $\mathrm{i}$ 天河流的流量。

对于每组测试用例，输出一行，格式为 "Case #x: M"，其中 $\mathrm{x}$ 是测试用例编号（从 $1$ 开始），$\mathbf{M}$ 是根据上述模型、与观测到的河流流量一致的最少农民数量。 如果你确定至少有一位农民在活动，但没有任何方式可以用遵守规则的农民来解释给定的输入，则输出 CHEATERS! 代替数字。

**样例解释** 第 1 组数据可以解释为有两条支流，没有农民从中取水。 第 2 组数据可以看作有一条支流，每隔 $4$ 天被取水一次。然而，这组数据的 $\mathbf D$ 是 $2$，所以这位农民违反了协议。 第 3 组数据可以看作有两位农民，各自的取水周期为 $4$ 天。 第 4 组数据可以看作有三位农民，取水周期分别为 $1, 2$ 和 $4$ 天。 **数据范围** - $1 \leq \mathbf{T} \leq 50$。 - $\mathbf{D}$ 是 $2$ 的幂。 - $1 \leq \mathbf{D} \leq \operatorname{floor}(\mathbf{N} / 2)$。 **小数据集（10 分）** - 时间限制：~~240~~ 5 秒。 - $1 \leq \mathbf{N} \leq 50$。 - $0 \leq \mathbf{d}_{\mathrm{i}} \leq 5$。 **大数据集（17 分）** - 时间限制：~~480~~ 10 秒。 - $1 \leq \mathbf{N} \leq 5000$。 - $0 \leq \mathbf{d}_{\mathrm{i}} \leq 1000$。 由 ChatGPT 4.1 翻译