华为 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)

if __name__ == "__main__":
    solve()

JavaScript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
});

rl.on('close', () => {
    if (lines.length === 0) return;
    
    // 读取第一行输入 n, x, y
    const firstLine = lines[0].split(/\s+/);
    if (firstLine.length < 3) return;
    const n = parseInt(firstLine[0]);
    const x = parseInt(firstLine[1]);
    const y = parseInt(firstLine[2]);
    
    // 读取第二行输入 a1, a2 ... an
    let a = [];
    if (lines.length > 1 && lines[1] !== '') {
        a = lines[1].split(/\s+/).map(Number);
    }
    
    // 题目要求选择 x 颗宝石，计算乘积大于等于 y 的组合数
    // 数据范围 n < 20，比较小，可以直接用递归暴力枚举
    let count = 0;
    
    // 递归函数生成组合
    function combine(startIndex, currentCount, currentProduct) {
        // 如果选够了 x 个宝石
        if (currentCount === x) {
            if (currentProduct >= y) {
                count++;
            }
            return;
        }
        
        // 遍历所有可能的组合
        for (let i = startIndex; i < n; i++) {
            // 剪枝优化：如果剩余的元素不足以填满 x 个，则不再继续
            if (n - i < x - currentCount) {
                break;
            }
            combine(i + 1, currentCount + 1, currentProduct * a[i]);
        }
    }
    
    combine(0, 0, 1);
    console.log(count);
});