28731번 - Этажи 스페셜 저지다국어

Артур Флек живет в очень старом доме: лифт не работает, а многие таблички с номерами этажей пришли в негодность. Артур очень устал и хочет поскорее попасть в свою квартиру.

В доме есть $n$ этажей, пронумерованных от $1$ до $n$. Между соседними этажами можно перемещаться по лестнице. Артур живет на этаже с номером $k$.

На некоторых этажах висят таблички с указанием номера этого этажа. Артур знает, что таблички присутствуют на $t$ этажах с номерами $a_1, a_2, \ldots, a_t$. Также известно, что на этажах с номерами $1$ и $n$ таблички есть.

Придя домой, Артур поднимался по лестнице, но задумался, и поэтому теперь он не знает, на каком этаже оказался. На каждом этаже он мог оказаться с вероятностью $\frac{1}{n}$. Артур не отличает этажи друг от друга и может ориентироваться только по табличкам с номерами. В том числе, если на этаже номер $k$ нет таблички, он не может отличить его от остальных этажей без табличек. Он хочет совершить как можно меньше переходов между этажами, попасть на этаж с номером $k$ и быть уверенным, что он оказался на этаже с номером $k$. Артур не очень сообразительный, поэтому пока он не дойдет до этажа с табличкой, он не может сделать никаких предположений о номере этажа, на котором сейчас находится.

Помогите Артуру найти оптимальную стратегию действий и определите математическое ожидание количества переходов между этажами, которое ему придется совершить.

В первой строке даны три целых числа $n$, $k$ и $t$ --- количество этажей в доме, этаж, на котором живет Артур, и количество этажей с табличками ($2 \le t \le n \le 100\,000$; $1 \le k \le n$).

Вторая строка содержит $t$ целых чисел $a_1, \ldots, a_t$ --- номера этажей, на которых есть таблички. Гарантируется, что $1 = a_1 < a_2 < \ldots < a_t = n$.

Выведите единственное вещественное число --- математическое ожидание количества переходов между этажами, которое придется совершить Артуру, чтобы попасть на этаж с номером $k$ при оптимальной стратегии, если изначально он может находиться на любом этаже с одинаковой вероятностью.

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

В первом тесте, если Артур изначально находится на этаже с номером $1$, $2$ или $4$, он сразу знает номер текущего этажа, и его оптимальной стратегией будет пойти в правильном направлении до желаемого этажа $3$. Если же Артур изначально находился на этаже номер $3$, он не знает об этом, потому что на нем нет таблички. Одной из оптимальных стратегий в этом случае будет подняться на один этаж вверх, узнать, что Артур оказался на этаже номер $4$, потому что на нем есть табличка, и спуститься обратно на один этаж. Поэтому, ответом будет $\frac{2 + 1 + 2 + 1}{4} = 1.5$.

Во втором тесте, если Артур оказался на этаже с номером $1$, $3$ или $5$, он знает его номер, и оптимальной стратегией будет просто пойти в правильном направлении до этажа с номером $3$. Иначе, он оказался на этаже с номером $2$ или $4$. В таком случае оптимальной стратегией будет спуститься на один этаж вниз. Если Артур был на этаже с номером $2$, он попадет на этаж с номером $1$, на котором висит табличка, поэтому дальше он просто сделает еще $2$ перехода и попадет на желаемый этаж номер $3$. Если же Артур был на этаже номер $4$, после перехода он окажется на этаже номер $3$, на котором висит табличка, поэтому он поймет, что пришел на желаемый этаж, и больше никуда не пойдет. В этом случае математическое ожидание количества переходов будет $\frac{2 + 3 + 0 + 1 + 2}{5} = 1.6$.