NOI '20 P4 - Dish

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

The chef is preparing m dishes, and each dish uses k grams of ingredients. As a result, the chef has bought n ingredients, and the ingredients are numbered 1, 2, \dots, n. The i-th ingredient weighs d_i grams. The sum of weights of all n ingredients is exactly m \times k grams. d_i and k are positive integers.

An ingredient may be used in multiple dishes. However, each dish may use at most 2 ingredients. Now you are asked to decide if there exists a valid way to prepare the m dishes. More formally, the final plan shall satisfy the following requirements:

  1. Prepare m dishes in total.

  2. Each dish uses at most 2 ingredients.

  3. Each dish uses exactly k grams of ingredients.

  4. For each ingredient used in a given dish, the amount used is a positive integer measured in grams.

  5. All of the n ingredients will be completely utilized.

If there exists a feasible solution, you should output a detailed plan.

Input Specification

In this problem, each test case may have multiple instances. The first line is an integer T denoting the number of instances. For each instance, the first line contains three positive integers n,m,k denoting the number of ingredients, the number of dishes to prepare, and the amount of ingredients each dish uses. The second line contains n integers, and the i-th integer denotes there are a_i grams of ingredient i.

Output Specification

For each instance, if there is no feasible solution, output -1. Otherwise, you need to output m lines, and each line specifies the way to prepare a dish. Depending on the number of ingredients used in the dish, a line shall be in one of the following two formats:

  • a line containing two integers i and x denoting the dish will use x grams of ingredient i. Here, 1 \le i \le n and x = k.
  • a line containing four integers i,x,j,y denoting the dish will use x grams of ingredient i and y grams of ingredient j. Here, 1 \le i,j \le n, i \ne j, x+y = k, x, y > 0.

Your answer will be checked by a special judge. Therefore, if there are multiple feasible solutions, you may print any solution. You should make sure the output is in the correct format, and two adjacent integers in a line are separated by a single space. Finally, your output shall not contain any extra characters.

Sample Input

1 1 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

Sample Output

1 10
1 80 2 20
2 10 3 90
4 100
1 5 5 95
1 20 4 80
2 30 6 70
3 50 6 50

For all test cases:
1 \le T \le 10, 1 \le n \le 500, n-2 \le m \le 5000, m \ge 1,
1 \le k \le 5000, \sum\limits_{i=1}^n d_i = m \times k.

Test case n m k
1~3 \le 4 \le 4 \le 50
4~5 \le 10 \le 10 \le 5000
6~7 \le 500 = n-1
8~9 n-1 \le m \le 5000
10 \le 25 \le 5000
11~12 \le 500
13~14 \le 50
15~17 \le 100 \le 5000
18~20 \le 500


There are no comments at the moment.