Угода чи ні#3176
«Угода чи ні» — це телевізійне ігрове шоу, яке проводиться у багатьох країнах світу. Давайте згадаємо правила гри.
На початку гри є кейсів, у кожному з яких знаходиться різна сума грошей. Лише особа, яка поклала гроші, знає, яка сума знаходиться у кожному кейсі. Гравець обирає один кейс, щоб залишити його собі, але не відкриває його. Далі гравець починає відкривати інші кейси у довільному порядку.
Перед тим як відкрити кожен кейс, у гру вступає банкір. Банкір пропонує гравцю певну суму грошей. Якщо гравець погоджується на пропозицію, він забирає запропоновану суму і гра закінчується. Інакше гра триває, і гравець відкриває черговий кейс. Коли у грі залишається лише два кейси, якщо гравець відмовляється від пропозиції, він може обрати один з двох кейсів і забрати суму, що у ньому. У будь-якому випадку гравець іде з гри з певною сумою грошей. Мета гравця — виграти якомога більше грошей. Мета банкіра — зробити так, щоб гравець пішов із якомога меншою сумою.
Вважається, що пропозиції банкіра ґрунтуються на такій поведінковій моделі гравця. Якщо банкір пропонує гравцеві суму , то ймовірність того, що гравець прийме пропозицію, розраховується так:
Тут та — це відповідно мінімальна і максимальна сума серед тих, що залишилися у грі. Допоможіть банкіру розрахувати математичне очікування тієї суми, з якою гравець піде, якщо банкір діятиме оптимально.
Перший рядок вхідних даних містить (2 \leq n \leq 16) — загальну кількість кейсів. Наступний рядок містить цілі числа a_1, a_2, \ldots, a_n — суми у кожному кейсі. Далі зазначено число (1 \leq q \leq 100) — кількість ситуацій, що цікавлять банкіра. Опис кожної ситуації наводиться в окремому рядку: (2 \leq k \leq n) — кількість сум, що залишились у грі; b_1, b_2, \ldots, b_k (1 \leq a_i, b_i \leq 10^6) — самі ці суми.
Для кожної ситуації виведіть очікуване значення суми, з якою гравець піде, а також оптимальну пропозицію банкіра. Обидва числа виводьте з точністю до двох знаків після коми.
Приклад 1