SP15434 UCV2013F - Life on Fornax

NASA 的超声波爬行飞船（简称 UCV）已经抵达天炉座的 UDFj-39546284 星系，并发现了一种奇特的细菌类生命形式。为此，我们计划采集样本并将其带回地球。然而，问题在于，当 UCV 回到地球时得确保这些细菌仍存活。以光速旅行大约需要 $13.42 \times 10^9$ 年，所以我们要仔细选择带回的细菌数量，确保在如此漫长的旅途中它们不会全部死亡。 在 UCV 的冷冻舱中，这些细菌遵循简单的繁殖规律，并且我们观察了它们离开冷冻舱后的行为。只是，目前我们缺少一个可以计算如此长时间内细菌数量变化的算法。好在，UCV 本身配备了一个虫洞插件安装系统，使得能够在几年内上传新的算法。 在冷冻舱中，细菌每年经过以下三个阶段： 1. **衰老阶段**：所有细菌年龄增加一年。 2. **繁殖阶段**：每只细菌分裂产生新的个体，新细菌年龄为 0 岁，而原细菌年龄至少为 1 岁。 3. **消亡阶段**：所有达到成熟年龄 $M$ 岁的细菌会死亡。 例如，假设成熟年龄为 2 岁，一只 0 岁和一只 1 岁的细菌经过一个周期后，会显示如下图所示的状态：  在冷冻繁殖阶段，不必担心细菌灭绝，因为新生的细菌数量总是等于或多于死亡的数量。然而，当冷冻舱打开后，细菌进入了一种奇特的减少阶段。每一轮减少中，年龄最大的一批 $R$ 个细菌会立即死亡；这个过程会持续到剩余细菌的数量少于 $R$ 个为止。特别需要注意的是，在某个时刻，细菌的数量如果恰好为 $R$ 个，那么它们会在那一刻全部死亡，从而造成灭绝。 NASA 要求你编写一个算法，这个算法将被上传到 UCV 上，以便计算出在地球上冷冻舱解冻后，仍然存活的细菌数量。

输入包含多个测试用例，每个测试用例对应一次模拟运行。对于每个测试用例，第一行包含三个整数，分别表示成熟年龄 $M$（$1 \le M \le 50$）、UCV 返回所需的年数 $Y$（$0 \le Y \le 10^{12}$）和减少规模 $R$（$1 \le R \le 10^9$），数值之间以空格分隔。紧接着的一行包含 $M$ 个整数，表示放入冷冻舱内的 0 岁到 $M-1$ 岁细菌的数量。 输入以 $M = Y = R = 0$ 作为结束标记。

对于每个测试用例，输出一行，表示经过减少过程后仍然存活的细菌数量。 **本翻译由 AI 自动生成**