시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

The Dwarf king Thrór wants to give some of his bars of gold to reward his k best warriors. The dwarf unit of currency is called a Mirian. Thrór has n different bars whose values in Mirians are {v1,...,vn}. He wants to give away a total target value of T Mirians to these warriors by handing out k gold bars. Not all of his warriors are equally deserving, and so they will generally receive bars of different values.

Thrór asks his brother Frór to help him to determine all the different ways in which he can form T as the sum of the values of k bars from his stock. For example, suppose that he has n = 10 bars of values V = {1, 2, 4, 5, 10, 11, 13, 15, 17, 19} Mirians, respectively. He wants to distribute k = 3 bars, and he wants to give a target amount of T = 20 Mirians. Frór determines that there are four different possible ways to do this:

1 + 2 + 17 1 + 4 + 15 2 + 5 + 13 4 + 5 + 11.

If, instead, there had been k = 4 warriors, there would be only two solutions:

1 + 2 + 4 + 13 1 + 4 + 5 + 10

You are to write a program to help brother Frór determine the number of solutions. Given the target amount T, the number of warriors k, and the values of bars V = {v1,...,vn}, your program is to output the number of different ways of forming T as the sum of k different values from V . If the number of solutions is 20 or fewer, your program should also list all the solutions in lexicographically increasing order. That is, all solutions involving the smallest bar are listed first, among those, solutions with the second smallest bar are listed first, and so on.

입력

The first line of the input file contains the number of test cases (≤ 100). Each case has the same format:

  • A line containing T, the desired target value, and k, the number of warriors. (You may assume that T ≤ 500 and k ≤ 50.)
  • A line containing n, the number of gold bars. (You may assume that n ≤ 100.)
  • The next n positive integers represent the values of the bars v1,...,vn. (You may assume that the values are distinct and are given in increasing order.)

You may assume that the number of solutions will fit into a single long integer, i.e., it will be less than 263-1.

출력

After computing the number of possible solutions, your program will output the number of solutions on a single line (preceded by the string “Number of solutions = ”). If this number is less than or equal to 20, it will then output each solution in lexicographically increasing order on a separate line, with the values separated by white spaces (blanks or tabs).

예제 입력 1

2
20 3
10
1 2 4 5 10 11 13 15 17 19
100 9
19
1 2 4 5 6 8 9 10 12 13 15 16 17 18 19 20 21 23 24

예제 출력 1

Test case 1
 Target sum = 20
 Number of warriors = 3
 V = {1, 2, 4, 5, 10, 11, 13, 15, 17, 19}
Number of solutions = 4
 1 2 17
 1 4 15
 2 5 13
 4 5 11

Test case 2
 Target sum = 100
 Number of warriors = 9
 V = {1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 17, 18, 19, 20, 21, 23, 24}
Number of solutions = 1491