Hide

Problem D
Bag of Tiles

You and your friend are playing a game involving chance, and you are interested in the odds of winning the game. The game proceeds as follows:

  • Your friend chooses $m$ tiles, each labeled with a positive integer. He shows them to you, and puts them in a bag. He then chooses an integer $0 \leq n \leq m$, and tells you what it is.

  • You choose an integer $t$ (the ‘target’), and tell your friend what it is.

  • Your friend reaches into the bag (without looking!) and draws out $n$ of the tiles, all at once.

  • If the sum of the drawn tiles equals $t$, you win. Otherwise, you lose.

Write a program that determines the odds of you winning at this game. Assume that, when drawing out $n$ tiles, each tile in the bag has the same probability of being chosen.

Input

Input starts with an integer $1 \leq g \leq 200$ indicating the number of games that follow. Each game description has three lines. The first contains an integer $0 < m \leq 30$, indicating the number of tiles in the bag. The second line contains $m$ labels of the tiles in the bag. Each tile’s label will be an integer in the range 1 to 10,000. The third line contains the two integers $n$ and $t$, where $0\leq n\leq m$ and $0\leq t < 10\, 000$.

Output

For each game, print the odds that you win that game. Print the odds in the form “Game $n$$a$ : $b$”, where $a$ represents the number of possible draws that would cause you to win, and $b$ represents the number of possible draws that would cause you to lose.

Sample Input 1 Sample Output 1
5
2
1 2
2 3
2
2 3
2 3
5
1 2 3 4 5
2 5
10
1 2 2 2 2 2 2 2 2 2
3 6
10
1 2 2 2 2 2 2 2 2 2
0 0
Game 1 -- 1 : 0
Game 2 -- 0 : 1
Game 3 -- 2 : 8
Game 4 -- 84 : 36
Game 5 -- 1 : 0

Please log in to submit a solution to this problem

Log in