AT_abc470_e [ABC470E] Concentration

Takahashi 正在玩一种类似于记忆配对的单人纸牌游戏。 共有 $2N$ 张牌。每张牌的正面都写有一个数字，背面没有写任何东西。 对于每一个满足 $1 \leq i \leq N$ 的 $i$，恰好有两张牌上写着 $A_i$（这些 $A_i$ 各不相同）。 Takahashi 按照以下流程玩这个游戏： - 将 $2N$ 张牌洗牌后面朝下摊开。 - 将 **life** 设为 $L$，**score** 设为 $0$。 - 重复以下步骤，直到 life 变为 $0$ 或桌上没有牌为止： - 选一张桌上面朝下的牌，将其翻开，记其数字为 $X$。 - 再选一张桌上面朝下的牌，将其翻开，记其数字为 $Y$。 - 如果 $X=Y$，则将这两张牌从桌上移除，得分增加 $X$。 - 如果 $X\neq Y$，则将这两张牌重新扣下，life 减 $1$。 请在 Takahashi 总是采取最优策略（期望分数最大化）的情况下，求出游戏结束时分数的期望值。 下面是更形式化的描述： - Takahashi 知道游戏的全部规则。 - Takahashi 知道 $A_1,\dots,A_N$ 的值。 - 记 $B$ 是通过对长度为 $2N$ 的序列 $(A_1,A_1,A_2,A_2,\ldots,A_N,A_N)$ 进行等概率随机排列后得到的序列。 - 起始时，Takahashi 对 $B$ 的内容一无所知。只要他了解了 $B_i$ 的值，就会一直记住。 - life 初始化为 $L$，score 初始化为 $0$，$S = \{1,2,3,\ldots,2N\}$。Takahashi 永远知道这些值。 - 不断重复以下步骤，直至 life 变为 $0$ 或 $S$ 为空： - 根据已获得的信息，Takahashi 从 $S$ 中选择一个元素 $i$。 - $B_i$ 的值被揭示，Takahashi 记住这个信息。 - 根据已获得的信息（包括 $B_i$ 的值），Takahashi 从 $S\setminus\{i\}$ 中再选一个元素 $j$。 - $B_j$ 的值被揭示，Takahashi 记住这个信息。 - 若 $B_i=B_j$，则从 $S$ 中移除 $i$ 和 $j$，并将 $B_i$ 加入到得分中。 - 若 $B_i\neq B_j$，则 life 减少 $1$。 - Takahashi 总是以最大化期望分数为目标采取最优策略。

输入为标准输入，格式如下： $N\ L\ A_1\ A_2\ \dots\ A_N$

输出答案。 若你的输出与标准答案的绝对误差或相对误差不超过 $10^{-5}$，则认为是正确的。

### 样例解释 1 游戏可能按如下方式进行。为方便区分六张牌，记为 `A`、`B`、`C`、`D`、`E`、`F`。 - 游戏开始时，life 为 $2$，score 为 $0$。 - 翻开卡牌 `A`，上面写着 $3$。 - 翻开卡牌 `B`，上面写着 $2$。 - 数字不相同，将两张牌重新扣下，life 变为 $1$。 - 翻开卡牌 `C`，上面写着 $3$。 - 翻开卡牌 `A`，上面写着 $3$。 - 数字相同，将两张牌从桌上移除，score 增加 $3$，现在 score 为 $3$。 - 翻开卡牌 `D`，上面写着 $1$。 - 翻开卡牌 `E`，上面写着 $2$。 - 数字不同，将两张牌重新扣下，life 变为 $0$。 - 由于 life 变为 $0$，游戏结束。分数为 $3$。 需要注意的是，在翻开卡牌 `C` 后，Takahashi 可以基于 "已知 `A` 上写着 $3$" 这一信息，选择翻开卡牌 `A`，形成配对。 ### 数据范围 - $1 \leq N \leq 200$ - $1 \leq L \leq 200$ - $1 \leq A_1 < A_2 < \dots < A_N \leq 10^5$ - 所有输入均为整数。 由 ChatGPT 5 翻译