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 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$.
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 |