C. Гелифиш и вечная фиалка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Перед Гелифиш находятся $$$n$$$ монстров, пронумерованных от $$$1$$$ до $$$n$$$. HP $$$i$$$-го монстра составляет $$$h_i$$$.

Гелифиш не хочет их убивать, но она хочет, чтобы эти монстры не представляли угрозу для нее. Поэтому она хочет уменьшить HP всех монстров до ровно $$$1$$$.

Теперь Гелифиш собирается атаковать монстров в течение $$$m$$$ раундов Мечом, Заточенным Слезами. В каждом раунде:

  1. Меч, Заточенный Слезами, светится с вероятностью $$$p$$$.
  2. Гелифиш может выбрать, атаковать или нет:
    • Если Гелифиш не атакует, ничего не происходит.
    • Если Гелифиш решает атаковать и Меч, Заточенный Слезами, светится, то HP всех монстров будет уменьшен на $$$1$$$.
    • Если Гелифиш решает атаковать и Меч, Заточенный Слезами, не светится, Гелифиш может выбрать одного из монстров и уменьшить его HP на $$$1$$$.

Обратите внимание, что прежде чем Гелифиш решит, атаковать или нет, она будет знать, светится ли меч или нет. Также, когда меч светится, Гелифиш может атаковать только всех монстров и не может атаковать только одного монстра.

Теперь Гелифиш хочет узнать, какова вероятность того, что она достигнет своей цели, если будет принимать оптимальные решения во время битвы.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$p'$$$ ($$$1 \leq n \leq 20$$$, $$$1 \leq m \leq 4000$$$, $$$0 \leq p' \leq 100$$$) — количество монстров, количество раундов атак и целое число, представляющее вероятность $$$p = \frac {p'} {100}$$$, что Меч, Заточенный Слезами, будет светиться.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$h_1,h_2,\ldots,h_n$$$ ($$$1 \leq h_i \leq 400$$$) — HP монстров.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$100$$$.

Выходные данные

Для каждого набора входных данных выведите одно действительное число, представляющее вероятность того, что Гелифиш достигнет своей цели.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.

Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Пример
Входные данные
4
2 2 10
2 2
5 5 20
2 2 2 2 2
6 20 50
1 1 4 5 1 4
9 50 33
9 9 8 2 4 4 3 5 3
Выходные данные
0.910000
0.672320
0.588099
0.931474
Примечание

В первом наборе входных данных в первом раунде Гелифиш всегда будет атаковать, независимо от того, светится ли меч или нет.

Если меч светится в первом раунде, то Гелифиш может достичь своей цели после атаки в первом раунде.

В противном случае, если меч не светится в первом раунде, она атакует монстра $$$1$$$. Для второго раунда:

  • Если меч светится, поскольку монстр $$$1$$$ был атакован в первом раунде, Гелифиш не сможет достичь своей цели.
  • В противном случае Гелифиш может атаковать монстра $$$2$$$, что позволит ей достичь своей цели.

Следовательно, вероятность того, что Гелифиш сможет достичь своей цели, составляет $$$10\% + (90\% \cdot 90\%) = 91\%$$$.

Во втором наборе входных данных Гелифиш будет атаковать только в первом раунде, в котором меч светится. Можно заметить, что единственный случай, при котором Гелифиш не сможет достичь своей цели — это если меч ни разу не будет светиться за все $$$5$$$ раундов. Вероятность того, что Гелифиш сможет достичь своей цели, составляет $$$100\% - (80\%)^5 = 67.232\%$$$.