| Codeforces Round 333 (Div. 1) |
|---|
| Закончено |
Клеофас участвует в n-тлоне — турнире, состоящим из n различных соревнований по n различным дисциплинам (пронумерованным от 1 до n). В n-тлоне m участников, и каждый из них участвует во всех соревнованиях.
По итогам каждого из n соревнований участникам присваиваются ранги от 1 до m таким образом, что никаким двум участникам не даётся одинаковый ранг, то есть ранги в каждом соревновании формируют перестановку чисел от 1 до m. Результат участника на соревновании равняется его/её рангу в нём, при этом чем хуже выступил участник, тем выше это значение.
Общий результат каждого участника высчитывается как сумма результатов этого участника по всем соревнованиям.
Итоговое место каждого участника равняется 1 + k, где k равняется количеству участников, у которых общий результат строго меньше общего результата данного участника.
Соревнования по n-тлону уже завершились, но результаты ещё не опубликованы. Клеофас помнит свои ранги в каждом конкретном соревновании, но ничего не помнит о том, как выступили другие участники. Исходя из этой информации, Клеофас хотел бы узнать математическое ожидание своего итогового места.
Все участники одинаково хороши во всех дисциплинах, так что в каждом соревновании все возможные исходы (перестановки рангов всех, кроме Клеофаса) равновероятны.
В первой строке входного файла записано два целых числа n и m (1 ≤ n ≤ 100, 1 ≤ m ≤ 1000) — количество соревнований и количество участников соответственно.
Далее следуют n строк, i-я из которых содержит целое число xi (1 ≤ xi ≤ m) — ранг Клеофаса в i-м соревновании.
Выведите единственное вещественное число — математическое ожидание итогового места Клеофаса. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 9.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
4 10
2
1
2
1
1.0000000000000000
5 5
1
2
3
4
5
2.7500000000000000
3 6
2
4
2
1.6799999999999999
В первом примере общий результат Клеофаса равняется 6. Ни один участник не может получить общий результат менее 6 (но возможно, что у другого участника тоже будет общий счет 6), поэтому итоговое место Клеофаса всегда будет 1.
