loj#P3342. 「NOI2020」制作菜品
「NOI2020」制作菜品
题目描述
厨师准备给小朋友们制作 道菜,每道菜均使用 克原材料。为此,厨师购入了 种原材料,原材料从 到 编号,第 种原材料的质量为 克。 种原材料的质量之和恰好为 克,其中 与 都是正整数。
制作菜品时,一种原材料可以被用于多道菜,但为了让菜品的味道更纯粹,厨师打算每道菜至多使用 种原材料。现在请你判断是否存在一种满足要求的制作方案。更具体地,方案应满足下列要求:
-
共做出 道菜。
-
每道菜至多使用 种原材料。
-
每道菜恰好使用 克原材料。
-
每道菜使用的每种原材料的质量都为正整数克。
-
种原材料都被恰好用完。
若存在满足要求的制作方案,你还应该给出一种具体的制作方案。
输入格式
从文件 dish.in
中读入数据。
本题单个测试点包含多组测试数据。
第一行一个整数 表示数据组数。对于每组数据:
-
第一行三个正整数 分别表示原材料种数、需要制作的菜品道数、每道菜品需使用的原材料的质量。
-
第二行 个整数,第 个整数表示第 种原材料的质量 。
输出格式
输出到文件 dish.out
中。
对于每组测试数据:
-
若不存在满足要求的制作方案,则输出一行一个整数 ;
-
否则你需要输出 行,每行表示一道菜品的制作方案,根据使用的原材料种数,格式为下列两种之一:
-
依次输出一行两个整数 和 ,表示该道菜使用 克第 种原材料制作。你应保证 。
-
依次输出一行四个整数 、、 和 ,表示该道菜使用 克第 种原材料与 克第 种原材料制作。你应保证 ,,,。
-
本题使用自定义校验器检验你的答案是否正确,因此若有多种满足条件的方案,你只需要输出任意一种。
你应保证方案输出的格式正确,且同一行中相邻的两个数使用单个空格分隔,除此之外你的输出中不应包含其他多余字符。
4
1 1 10
10
4 3 100
80 30 90 100
5 3 1000
200 400 500 900 1000
6 4 100
25 30 50 80 95 120
1 10
1 80 2 20
2 10 3 90
4 100
-1
1 5 5 95
1 20 4 80
2 30 6 70
3 50 6 50
数据范围与提示
对于所有测试点:
,,,,
,。
每个测试点的具体限制见下表:
测试点编号 | |||
---|---|---|---|