题解：杂货店问题（Grocery Store, POJ 3369）

一、题目分析

本题要求找出四个价格（精确到分，即两位小数），使得它们的和等于积，且总和不超过20欧元。关键在于高效枚举所有可能的四元组组合，并验证其合法性。

二、核心思路

1. 数学转换：

   • 将价格转换为整数（乘以100，避免浮点数误差）。
   • 问题转化为：找到四个整数 (a, b, c, d)，满足 (a + b + c + d = a \times b \times c \times d) 且 (a + b + c + d \leq 2000)。

2. 枚举优化：

   • 按升序枚举 (a \leq b \leq c \leq d)，减少重复计算。
   • 利用数学关系推导枚举范围：
     • (a) 的上限为 (125)（因为 (a \leq 2000/4 = 500)，但实际需满足后续条件）。
     • (b) 的上限为 (666)（结合 (a + b + c + d \leq 2000)）。
     • (c) 的上限为 (1000)，并动态检查 (a + b + c < 2000)。

3. 快速验证：

   • 计算 (x = a + b + c) 和 (y = a \times b \times c)。
   • 通过整除性判断 (d = \frac{1000000x}{y - 1000000}) 是否为整数，并验证 (d \geq c) 且 (x + d \leq 2000)。

三、代码解析

#include <iostream>
using namespace std;
typedef int INT;

int main()
{
    INT x, y, d;
    // 枚举a，范围1~125
    for (INT a = 1; a <= 125; ++a)
        // 枚举b，范围a~666，且a+b<2000
        for (INT b = a; b <= 666 && a + b < 2000; ++b)
            // 枚举c，范围b~1000，且a+b+c<2000
            for (INT c = b; c <= 1000 && (x = a + b + c) < 2000; ++c) {
                // 关键条件：若a*b*c <=1000000，跳过（避免d为负数或零）
                if ((y = a * b * c) <= 1000000)
                    continue;
                // 判断d是否为整数
                if (1000000 * x % (y - 1000000))
                    continue;
                // 计算d
                d = 1000000 * x / (y - 1000000);
                // 验证d的有效性：总和不超过2000且d>=c
                if (x + d > 2000 || d < c)
                    continue;
                // 输出结果，格式化为两位小数
                printf("%d.%02d %d.%02d %d.%02d %d.%02d\n",
                       a / 100, a % 100, b / 100, b % 100,
                       c / 100, c % 100, d / 100, d % 100);
            }
}

四、关键点详解

1. 枚举范围优化：

   • a的上限：通过数学推导和试错确定为125，避免无效计算。
   • b和c的上限：结合总和约束动态调整，减少枚举次数。

2. 整除性判断：

   • 1000000 * x % (y - 1000000) 确保 (d) 为整数，避免浮点数误差。

3. 条件过滤：

   • y > 1000000 防止分母为负数或零，确保 (d) 为正数。
   • d >= c 保证四元组的升序排列，避免重复解。

4. 输出格式：

   • %d.%02d 确保每个价格正确显示为两位小数（如125 → 1.25）。

五、复杂度分析

• 时间复杂度：约为 (O(125 \times 666 \times 1000) \approx 8.3 \times 10^7)，在可接受范围内。
• 空间复杂度：(O(1))，仅需常数空间存储变量。

该解法通过数学优化和枚举剪枝，高效地找出所有符合条件的四元组，确保在题目约束下快速生成结果。