P6775 [NOI2020] 制作菜品
题目描述
厨师准备给小朋友们制作 $m$ 道菜,每道菜均使用 $k$ 克原材料。为此,厨师购入了 $n$ 种原材料,原材料从 $1$ 到 $n$ 编号,第 $i$ 种原材料的质量为 $d_i$ 克。$n$ 种原材料的**质量之和恰好为 $m \times k$ 克**,其中 $d_i$ 与 $k$ 都是**正整数**。
制作菜品时,一种原材料可以被用于多道菜,但为了让菜品的味道更纯粹,厨师打算每道菜**至多使用 $2$ 种**原材料。现在请你判断是否存在一种满足要求的制作方案。更具体地,方案应满足下列要求:
- 共做出 $m$ 道菜。
- 每道菜至多使用 $2$ 种原材料。
- 每道菜恰好使用 $k$ 克原材料。
- 每道菜使用的每种原材料的质量都为正整数克。
- $n$ 种原材料都被恰好用完。
若存在满足要求的制作方案,你还应该给出一种具体的制作方案。
输入格式
无
输出格式
无
说明/提示
#### 样例 1 解释
对于第二组数据,一种满足要求的制作方案为:
- 使用 $80$ 克原材料 $1$ 与 $20$ 克原材料 $2$ 做第一道菜。
- 使用 $10$ 克原材料 $2$ 与 $90$ 克原材料 $3$ 做第二道菜。
- 使用 $100$ 克原材料 $4$ 做第三道菜。
#### 样例 2
见选手目录下的 dish/dish2.in 与 dish/dish2.ans。
#### 样例 3
见选手目录下的 dish/dish3.in 与 dish/dish3.ans。
---
### 测试点约束
对于所有测试点:
$1 \leq T \leq 10$,$1 \leq n \leq 500$,$n - 2 \leq m \leq 5000$,$m \geq 1$,$1 \leq k \leq 5000$,$\sum_{i=1}^{n}d_i = m \times k$。
每个测试点的具体限制见下表:
| 测试点编号 | $n$ | $m$ | $k$ |
| :-: | :-: | :-: | :-: |
| $1\sim 3$ | $\le 4$ | $\le 4$ | $\le 50$ |
| $4\sim 5$ | $\le 10$ | $\le 10$ | $\le 5\times 10^3$ |
| $6\sim 7$ | $\le 500$ | $=n-1$ | $\le 5\times 10^3$ |
| $8\sim 9$ | $\le 500$ | $n-1\le m\le 5\times 10^3$ | $\le 5\times 10^3$ |
| $10$ | $\le 25$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ |
| $11\sim 12$ | $\le 25$ | $\le 5\times 10^3$ | $\le 500$ |
| $13\sim 14$ | $\le 50$ | $\le 5\times 10^3$ | $\le 500$ |
| $15\sim 17$ | $\le 100$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ |
| $18\sim 20$ | $\le 500$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ |