SP25475 TAP2015E - Perfect packing

在工业饼干生产线上，最难自动化的环节之一是包装。目标是设计一个能精确计数 **G** 个饼干的装置，将它们放入一个包装中，而难点在于这些饼干的形状可能各异，比如各种动物形状。 你所在的饼干工厂的设计团队未能成功解决这个问题。当前的设计是一个计数机，激活时，它以概率 **P $_{i}$** 选取 **C $_{i}$** 个饼干，其中 **i = 1, 2, ..., K**。由于项目预算已用尽，你需要另寻办法使这个装置发挥作用。 你有了一个新的主意来拯救这个项目。你将使用 **N** 台这种计数机，并借助一个特定的软件进行以下迭代过程。在第一次迭代前，**N** 台计数机都被激活，每台选择一定数量的饼干。在每次迭代中，软件会挑选出一个非空的计数机子集 **S**，使得这种选择的饼干数量总和最接近所需的 **G**（即绝对差最小）。如果有多个子集符合条件，软件会以均匀概率随机选择其中一个作为 **S**。由 **S** 中计数机选择的饼干会被移除并打包在一起，随后 **S** 内的计数机会重新激活，而 **S** 外的计数机保持上次选择的状态不变。这个过程一直持续，直到成功生产出 **M** 个包装为止。 例如，有 **N = 3** 台计数机，分别是 **m $_{1}$, m $_{2}$** 和 **m $_{3}$**。每台都可以选择 **C $_{1}$ = 1** 或 **C $_{2}$ = 2** 个饼干，概率分别为 **P $_{1}$ = P $_{2}$ = ½**。如果需要生产 **M = 2** 个每包 **G = 5** 个饼干的包装，一种可能的情况是：三台机器在开始前选择 **C $_{2}$ = 2** 个饼干（概率为 **½ * ½ * ½ = ⅛**）。在第一次迭代中，软件可以选择子集 **{m $_{1}$, m $_{2}$, m $_{3}$}**、**{m $_{1}$, m $_{2}$}**、**{m $_{1}$, m $_{3}$}** 和 **{m $_{2}$, m $_{3}$}**，每种选择的概率为 **¼**，因为它们都使得与 **G = 5** 的差距仅为一个饼干。假设选中了子集 **S = {m $_{2}$, m $_{3}$}**，那么由 **m $_{2}$** 和 **m $_{3}$** 选择的四个饼干会被打包。这两台机器会再次激活，可能 **m $_{2}$** 选 **C $_{1}$ = 1**，**m $_{3}$** 选 **C $_{2}$ = 2**（概率为 **½ * ½ = ¼**）。此时，第一次迭代结束，计数机 **m $_{1}$, m $_{2}$ 和 m $_{3}$** 分别有 **2, 1** 和 **2** 个饼干。在第二次迭代中，软件必须选择子集 **S = {m $_{1}$, m $_{2}$, m $_{3}$}**，因为它们正好有五个饼干，随后会打包起来。第三次激活后，流程结束，成功生产出 **M = 2** 个包装。注意，过程的总体概率为 **⅛ * ¼ * ¼ = 1/128**，这种情况下，每个包装的平均饼干数量是 **4.5**（因为一个包装有四个饼干，另一个有五个饼干）。 你的老板对这个系统的可行性仍有些怀疑，因此希望你能提供一个具体的验证过程。你只需要计算连续生产 **M** 个包装后，每个包装的期望饼干数量即可，假设 **N** 台计数机总是按照给定的概率选取饼干。

输入包含多个测试用例。每个测试用例的第一行有四个整数 **N, K, G** 和 **M**。其中 **N** 是所用计数机的数量（1 ≤ N ≤ 10），**K** 是每个计数机可以选取的饼干数量类数目（1 ≤ K ≤ 5），**G** 是每个包装内希望的饼干数量（1 ≤ G ≤ 100），**M** 是计划生产的包装总数（1 ≤ M ≤ 100）。接下来的 **K** 行中，每行包含一个整数 **C $_{i}$** 和一个有理数 **P $_{i}$**，表示计数机会以概率 **P $_{i}$** 选取 **C $_{i}$** 个饼干（1 ≤ C $_{i}$ ≤ 100 且 0 < P $_{i}$ ≤ 1，**P $_{i}$** 精确到小数点后两位）。注意，**C $_{i}$** 对于不同的 **i** 是不一样的，并且所有概率之和为 1。

对于每个测试用例，输出一行，表示按题目描述生产 **M** 个包装后的每个包装中饼干的期望数量。结果需保留六位小数，必要时进行四舍五入。 **本翻译由 AI 自动生成**