CF2068D Morse Code

莫尔斯电码是一种经典的远程通信方式，但存在某些缺陷会增加长消息的传输时间。 在莫尔斯电码中，字母表中的每个字符被分配一个由点（.）和划（-）组成的序列，且没有序列是另一个序列的前缀。传输字符串时，各字符对应的序列按顺序发送。划的传输时间是点的两倍。 你的字母表包含 $n$ 个字符，其中第 $i$ 个字符在你的语言中出现频率为 $f_i$。你的任务是设计一个莫尔斯电码编码方案，为每个字符分配点划序列，以最小化单个字符的期望传输时间。即你需要最小化 $f_1t_1 + f_2t_2 + \cdots + f_nt_n$，其中 $t_i$ 是传输第 $i$ 个字符序列所需的时间。

第一行包含一个整数 $n$（$2 \le n \le 200$）——字母表中字符的数量。 第二行包含 $n$ 个实数 $f_1, f_2, \ldots, f_n$（$0 < f_i < 1$）——第 $i$ 个字符的频率。所有 $f_i$ 值精确到小数点后四位。所有频率之和严格等于 $1$。

输出 $n$ 行，每行包含一个由点（.）和划（-）组成的字符串。第 $i$ 行对应第 $i$ 个字符的编码序列。 若存在多个具有相同最小期望传输时间的有效编码方案，输出任意一种均可。

第一个样例中，字母表包含三个字符（例如 $a$, $b$, $c$），频率分别为 $0.3$, $0.6$, $0.1$。在最优方案中，$a$ 对应 `-.`，$b$ 对应 `.`，$c$ 对应 `--`。此时期望传输时间为 $0.3 \cdot 3 + 0.6 \cdot 1 + 0.1 \cdot 4 = 1.9$ 时间单位/字符，这是最优解。 作为对比，若分配 $a\to$ `..`，$b\to$ `-`，$c\to$ `.-`，则期望传输时间为 $0.3 \cdot 2 + 0.6 \cdot 2 + 0.1 \cdot 3 = 2.1$。而分配 $a\to$ `-`，$b\to$ ` .`，$c\to$ `..` 虽然期望传输时间更低，但该方案无效，因为 `.` 是 `..` 的前缀。 翻译由 DeepSeek R1 完成