151. 偏好A5纸(A Preference for A5)

一家印刷店每周处理 16 个批次（作业），每个批次需要一张 A5 尺寸的特殊校样纸。

每个星期一早晨，主管打开一个新信封，里面有一张 A1 尺寸的特殊纸张。

主管将其对半裁开，得到两张 A2 尺寸的纸张。然后将其中一张对半裁开，得到两张 A3 尺寸，以此类推，直到得到本周第一个批次所需的 A5 尺寸纸张。

所有未使用的纸张都放回信封中。

在每个后续批次开始时，主管从信封中随机取出一张纸。如果是 A5 尺寸，则直接使用。如果更大，则重复"对半裁开"过程直到得到一张 A5 尺寸的纸张，剩余纸张始终放回信封。

求一周内（不包括第一个和最后一个批次），主管发现信封中只有一张纸的次数的期望值。

答案保留六位小数，格式为 x.xxxxxx。

分析：用概率传播 DP 建模。状态为四种尺寸纸张的数量 \((a_2,a_3,a_4,a_5)\)，初始状态为第 1 批次结束后的 \((1,1,1,1)\)。每批随机抽取一张并裁切，根据抽到的尺寸产生不同的转移。对第 2 到第 15 批次，累加信封中仅有一张纸的概率。

一、数学背景

A 系列纸张的面积满足：1 张 A1 = 2 张 A2 = 4 张 A3 = 8 张 A4 = 16 张 A5。以 A5 为单位，初始 A1 等价于 16 个 A5。每消耗一批，面积减少 1。状态 \((a_2,a_3,a_4,a_5)\) 满足面积守恒：

其中 \(k\) 为已完成的批次数。

第 1 批后（\(k=1\)），状态为 \((1,1,1,1)\)，总面积 \(8+4+2+1=15\)。

二、算法设计

设 \(n=a_2+a_3+a_4+a_5\) 为当前信封中纸张总数。

从状态 \((a_2,a_3,a_4,a_5)\) 出发，下一批次的四种可能转移：

• 抽到 A5（概率 \(a_5/n\)）：消耗 A5，新状态 \((a_2,a_3,a_4,a_5-1)\)。
• 抽到 A4（概率 \(a_4/n\)）：A4 裁为两张 A5，消耗一张，放回一张 A5。新状态 \((a_2,a_3,a_4-1,a_5+1)\)。
• 抽到 A3（概率 \(a_3/n\)）：A3 裁为两张 A4，一张 A4 再裁为两张 A5，消耗一张 A5。放回一张 A4 和一张 A5。新状态 \((a_2,a_3-1,a_4+1,a_5+1)\)。
• 抽到 A2（概率 \(a_2/n\)）：A2 裁为两张 A3，一张 A3 再裁为两张 A4，一张 A4 再裁为两张 A5。消耗一张 A5，放回一张 A3、一张 A4 和一张 A5。新状态 \((a_2-1,a_3+1,a_4+1,a_5+1)\)。

使用字典存储状态→概率分布。初始分布为 {(1,1,1,1): 1.0}。对第 2 到第 15 批（共 14 批），累加 \(\sum(\text{counts})=1\) 的状态概率，再转移到下一分布。

三、复杂度分析

状态数受面积约束限制，最大值约数十个。14 步转移，总运算量极小。实测约 65 毫秒。

四、代码实现与说明

"""
Project Euler Problem 151: A Preference for A5

Compute the expected number of times (excluding first and last batch)
that the envelope contains exactly one sheet of paper at the start of a batch.
"""

from collections import defaultdict


def solve() -> float:
    """
    Simulate the probability distribution over states for batches 2 through 15.

    State: (a2, a3, a4, a5) = counts of A2, A3, A4, A5 sheets in the envelope.
    Initial state (after batch 1): (1, 1, 1, 1).
    """
    dist = {(1, 1, 1, 1): 1.0}
    expected_singles = 0.0

    for _ in range(14):
        for state, prob in dist.items():
            if sum(state) == 1:
                expected_singles += prob

        next_dist = defaultdict(float)
        for (a2, a3, a4, a5), prob in dist.items():
            total_sheets = a2 + a3 + a4 + a5
            if total_sheets == 0:
                continue

            if a5 > 0:
                p = prob * a5 / total_sheets
                next_dist[(a2, a3, a4, a5 - 1)] += p

            if a4 > 0:
                p = prob * a4 / total_sheets
                next_dist[(a2, a3, a4 - 1, a5 + 1)] += p

            if a3 > 0:
                p = prob * a3 / total_sheets
                next_dist[(a2, a3 - 1, a4 + 1, a5 + 1)] += p

            if a2 > 0:
                p = prob * a2 / total_sheets
                next_dist[(a2 - 1, a3 + 1, a4 + 1, a5 + 1)] += p

        dist = next_dist

    return expected_singles


if __name__ == "__main__":
    result = solve()
    print(f"{result:.6f}")

代码说明（按执行顺序）：

导入

• defaultdict 用于初始化概率分布中不存在的状态为概率 0。

solve

• dist 为字典，键是四元组 \((a_2,a_3,a_4,a_5)\)，值是该状态的概率。初始化为 {(1,1,1,1): 1.0}。
• expected_singles 累加单张纸事件的期望次数。

主循环（14 次迭代）

• 每轮对应一个批次（第 2 到第 15 批）。

累加单张概率

• 遍历当前分布中所有状态，若 sum(state) == 1（纸张总数为 1），将状态概率累加到 expected_singles。

状态转移

• 对每个状态，计算 total_sheets 为四种纸张的数量和。
• 若 total_sheets == 0（空信封，不应出现），跳过。
• 按四种抽纸情形计算转移概率 \(p = \text{prob} \times \frac{\text{count}}{\text{total_sheets}}\)，累加到 next_dist 的对应新状态中。
• 转移规则对应抽到 A5（直接消耗）、A4（裁切并放回一张 A5）、A3、A2 四种情形。

输出

• 以 6 位小数格式打印结果。