华为 OD 机试真题：挑选宝石 Python & JS 实现

题目

游乐园有一款互动游戏，游戏开始时会提供 n 个宝石，每个宝石都有一个属性值 a1, a2... an。玩家在游戏前可以挑选 x 颗宝石，将这些宝石的属性值相乘组成玩家的属性值。游戏玩家需要 y 点属性值，请帮助游戏玩家计算有多少种计算方式。

输入描述 第一行：三个整数 n, x, y

• 第一个整数 n (0 < n < 20) 表示宝石总数量。
• 第二个整数 x (0 < x <= n)，表示可以选择宝石个数。
• 第三个整数 y，表示通过游戏需要的属性值。

第二行：n 个整数，a1, a2... an (-100 < ai < 100)，表示每个宝石的属性值。

输出描述 输出一个整数，表示玩家可以通过游戏的挑选方式的数量。

示例 1 输入： 4 2 8 2 -3 4 5

输出： 3

思路

题目中 N 的取值范围较小 (N < 20)，可以直接使用组合数学的方法暴力枚举所有可能的宝石组合，计算乘积并判断是否大于等于 Y 即可。

Code

Python

import sys
from itertools import combinations

def solve():
    line1 = sys.stdin.readline().strip()
    if not line1:
        return
    n, x, y = map(int, line1.split())
    
    # 读取第二行输入 a1, a2 ... an
    line2 = sys.stdin.readline().strip()
    if not line2:
        a = []
    else:
        a = list(map(int, line2.split()))
    
    # 题目要求选择 x 颗宝石，计算乘积大于等于 y 的组合数
    # 数据范围 n < 20，比较小，可以直接用 itertools.combinations 暴力枚举
    count = 0
    # 遍历所有长度为 x 的组合
    for combo in combinations(a, x):
        product = 1
        for val in combo:
            product *= val
        if product >= y:
            count += 1
    print(count)

 __name__ == :
    solve()