New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2147: 石子切割

内存限制：512 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：1
提交提交记录统计

题目描述

现在有 n 个石子，第 i 个石子重量为 w[i]。
你可以对石子进行切割，使其变成两部分，切割后的石子仍可以被继续切割。
要求切割次数最小，同时对所有石子进行分组，每组重量恰好为 k。
例如 k = 8 时，给定石子为：2, 4, 5, 6, 7。
只需要将石子 5 切割成 1 + 4，就可以变成：2, 4, 1, 4, 6, 7。
这样可以进行分组：2 + 6、4 + 4、1 + 7，保证每组重量均为 8。

输入格式

第一行为正整数 n 和 k，1≤n≤100,1≤k≤8。
第二行为 n 个正整数，w[1],...,w[n]，1≤w[i]≤1000000。
输入保证所有石子重量之和为 k 的倍数。

输出格式

输出最小分割次数。

输入样例 复制 

样例1：
5 8
2 4 5 6 7

样例2：
2 5
12 13

输出样例 复制 

样例1：
1

样例2：
4

数据范围与提示

来源：2022.BAPC