← 返回题目列表

Codeforces · 2068/D

D. 摩尔斯电码

中文机器翻译题面 查看原题

摩尔斯电码是一种经典的长距离通信方式,但存在一些缺点,会增加长消息的传输时间。

在摩尔斯电码中,字母表中的每个字符都分配有一系列点和破折号,使得 没有序列是另一个序列的前缀。为了传输一串字符,每个字符对应的序列按顺序发送。 破折号的传输时间是点的两倍。

您的字母表有 $$$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 \lt f_i \lt 1$$$) — $$$f_i$$$ 是第 $$$i$$$ 个字符的频率。所有值 $$$f_1$$$、$$$f_2$$$、$$$\ldots$$$、$$$f_n$$$ 均精确到小数点后四位数字。所有频率的总和恰好为 1。

输出

打印 $$$n$$$ 行,每行包含一个由点 $$$\texttt{.}$$$ 和破折号 $$$\texttt{-}$$$ 组成的字符串。第 $$$i$$$ 行对应于您分配给第 $$$i$$$ 字符的点和破折号序列。

如果存在多个具有最小可能预期传输时间的有效分配,则其中任何一个都被认为是正确的。

示例

输入
复制

3
0.3000 0.6000 0.1000

输出
复制

-.
.
--

输入
复制

3
0.3000 0.4500 0.2500

输出
复制

..
-
.-

注意

在 第一个样本,字母表包含三个字母,例如 $$$a$$$、$$$b$$$ 和 $$$c$$$,频率分别为 $$$0.3$$$、$$$0.6$$$ 和 $$$0.1$$$。在最优分配中,我们将 $$$a$$$ 分配给 '$$$\texttt{-.}$$$',将 $$$b$$$ 分配给 '$$$\texttt{.}$$$',将 $$$c$$$ 分配给 '$$$\texttt{--}$$$'。这给出了每个字符 $$$0.3 \cdot 3 + 0.6 \cdot 1 + 0.1 \cdot 4 = 1.9$$$ 时间单位的预期传输时间,这是最佳的。

为了进行比较,赋值 $$$a\to$$$ '$$$\texttt{..}$$$'、$$$b \to$$$ '$$$\texttt{-}$$$'、$$$c \to$$$ '$$$\texttt{.-}$$$' 的预期传输时间为 $$$0.3 \cdot 2 + 0.6 \cdot 2 + 0.1 \cdot 3 = 2.1$$$。赋值 $$$a \to$$$ '$$$\texttt{-}$$$'、$$$b \to$$$ '$$$\texttt{.}$$$'、$$$c \to$$$ '$$$\texttt{..}$$$' 的预期传输时间较短,但无效,因为 '$$$\texttt{.}$$$' 是'$$$\texttt{..}$$$'。