#2081. #6191. 「美团 CodeM 复赛」配对游戏
#6191. 「美团 CodeM 复赛」配对游戏
说明
有 nnn 个人排成一排,一开始全部面向前方,然后随机朝左或是朝右转。
然后我们不断审查这个队列,每次选择两个面对面的相邻的人,将他们从队列中取出。
例如(>
表示向右,<
表示向左):
- 队列
>>><<<
的消除过程为,>>><<<
到>><<
到><
到空队列(每次去除一对)。 - 队列
>><><<<>
的消除过程为,>><><<<>
到>><<<>
到><<>
到<>
(每次去除一对)。
求最后期望能够剩下多少人。
输入格式
一行一个正整数 nnn 。
输出格式
一行一个实数,表示期望剩下的人数,四舍五入保留三位小数。
样例
样例输入
10
样例输出
4.168
数据范围与提示
1≤n≤20001\le n\le 20001≤n≤2000
样例