Chess Tournament
Турнир за Купата на Декана 2018
Time Limit: 0.5s, Memory Limit: 64MiB
Ели участва в турнир по шах. В него са се включили N човека (броейки и нея), за всеки от които се знае техният текущ ELO рейтинг (число, определящи колко добър е всеки от тях). За целите на тази задача ще считаме, че ако двама участника с рейтинг, съответно, X и Y играят един срещу друг, то първият има шанс да победи X / (X + Y), а вторият има шанс Y / (X + Y).

Турнирът протича на рундове. В началото участниците се нареждат в редица, а на всеки рунд двама стоящи един до друг участници биват избрани на случаен принцип и изиграват партия шах. Загубилият си тръгва (като вече считаме, че не присъства в редицата с участници). Този, който до сега е стоял отляво на него (ако има такъв) и този, който до сега е стоял отдясно на него (ако има такъв) вече "стоят един до друг", тоест могат да играят помежду си. След изиграване на N-1 рунда (партии шах) в редицата остава само един човек, който е обявен за победител.

Ели знае рейтингите R1, R2, ..., RN на всеки от участниците в турнира, както и позицията си K в редицата. Сега момичето ви пита какъв е шансът да спечели турнира?
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и K - съответно броят участници и позицията на Ели (броено от левия край на редицата). На следващия ред ще бъдат зададени N цели числа R1, R2, ..., RN - рейтингът на всеки от участниците в реда, в който са застанали в редицата.
Изход
На стандартния изход изведете едно число с плаваща запетая - шансът Ели да спечели турнира. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ KN ≤ 100
  • 1 ≤ Ri ≤ 3,000
Примерен Вход Примерен Изход
4 3 2042 1917 2018 2101 0.186071134564
11 5 66 13 17 11 42 19 23 71 72 33 57 0.077905622628
В първия пример участват 4 играча, като Ели е този с рейтинг 2018. За да спечели, тя със сигурност трябва да бие играча, който се намира отдясно на нея. Това става със шанс 2018/(2018+2101) = 0.489924739014.
Има два варианта за останалите два мача:
  1. Ели да играе и с двамата последователно, като има шанс за печалба 2018/(2018+1917) * 2018/(2018+2042) = 0.254901008381
  2. Първо двамата да играят помежду си, а после Ели да играе с победителя, като тогава нейните шансове биха били 2042/(2042+1917) * 2018/(2018+2042) + 1917/(1917+2042) * 2018/(2018+1917) = 0.504689678705

Така вероятността да спечели турнира е:
0.489924739014 * (1/2 * 0.254901008381 + 1/2 * 0.504689678705) = 0.186071134564
Мрън!