Deal or No Deal#3176
Deal or No Deal is a television game show played in many countries around the world. Let's review the rules of the game.
At the beginning of the game, there are briefcases, each containing a different amount of money. Only the person who placed the money knows which amount is in which briefcase. The player chooses one briefcase to keep for themselves but does not open it. The player then begins to open the other remaining briefcases in any order.
Before each briefcase is opened, the banker enters the game. The banker offers the player a certain sum of money. If the player accepts the offer, they take the money offered and end the game. Otherwise, they continue opening briefcases. When only two briefcases remain in the game, if the player declines the offer, they can choose one of the two remaining briefcases and take the amount inside. In any case, the player leaves the game with a certain amount of money. The player's goal is to win as much as possible. The banker's goal is to make the player leave with as little as possible.
Suppose the banker's offer follows the following behavioral model of the player. If the banker offers the player an amount , then the probability that the player accepts the offer is calculated as:
Here, and are the minimum and maximum amounts remaining in the game, respectively. Help the banker calculate the expected value that the player will take if the banker offers optimal deals.
The first line of input contains (2 \leq n \leq 16) — the total number of briefcases. The next line contains the integers a_1, a_2, \ldots, a_n — the amounts in each briefcase. Then follows the number (1 \leq q \leq 100) — the number of situations of interest to the banker. Each following line describes a situation: (2 \leq k \leq n) — the number of amounts remaining in the game; b_1, b_2, \ldots, b_k (1 \leq a_i, b_i \leq 10^6) — the remaining amounts.
For each situation, output the expected value of the amount the player is going to win, and also the optimal offer the banker should make. Both numbers should be printed rounded to two decimal places.
Example 1