← 返回题目列表

AtCoder · abc031_d

D. 单词组合

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

問題文

日本有一种制作双关语的文化,将数字与短字母串相匹配。

对此感兴趣的高桥先生,1 以上 K 仅由以下数字组成的正整数 v_1, v_2, ... , v_N 以及每个正整数对应的字符串 w_1, w_2, ... , w_N 设置 (v_1, w_1), (v_2, w_2), ... , (v_N, w_N)来推断哪些数字对应于哪些字符串。

也就是说满足以下条件 K 字符串 我想找到 s_1, s_2, ... , s_K 。 满足

  • 1≦i≦K 的任何整数 对于 i ,1≦|s_i|≦3 满意。 对于
  • 1≦i≦N 的任何整数 对于 i ,一个整数 将 v_i 分解为数字后得到的数字按照从上到下的顺序显示。 当使用 d_1, d_2, ... , d_l 时,字符串 按此顺序与 s_{d_1}, s_{d_2}, ... , s_{d_l} 连接的字符串是 等于 w_i 。 创建一个输出

K 字符串 我想找到 s_1, s_2, ... , s_K 的程序。


入力

输入是按以下格式从标准输入给出的。

K N
v_1 w_1
v_2 w_2
:
v_N w_N
  • 1 行包含一个整数 K (1≦K≦9) 和 我讨厌 N (1≦N≦50) 用空格分隔。
  • 2 在 N 行提供有关数字和字符串对的信息。N 行数过多 i (1≦i≦N) 在线 1 以上 K 仅由以下数字组成的整数: 仅由 v_i (1≦v_i≦10^9) 和半角小写字母组成的字符串 w_i (1≦|w_i|≦27) 用空格分隔。
  • 1 以上 K 以下任意数字 v_1, v_2, ... , v_N 出 1 出现多次。
  • 对于给定的输入,满足条件 K 字符串 我想找到 s_1, s_2, ... , s_K 始终存在。 任何直到

部分点

针对此问题设置了部分分数。

  • K ≦ 3 和 w_1 从 w_N 的字符串 仅包含 a, b, c 的数据集 1 ,40 点。
  • 没有附加约束的数据集 如果您对 2 的回答正确,除上述之外, 60 点。

出力

输出是 K 行组成。K 行数过多 i (1≦i≦K) 行是一个字符串 输出 s_i 。

满足条件 如果 K 字符串有多种组合,则哪个组合 1 你可以输出一个。

还在输出末尾添加换行符。


入力例1

6 4
356 migoro
461 yoroi
2 ni
12 ini

出力例1

i
ni
mi
yo
go
ro

在此输入示例中,s_1 = i, s_2 = ni, s_3 = mi, s_4 = yo, s_5 = go, s_6 = ro 满足标题的意思。 可以是 K 字符串。事实上, 当

  • v_1 = 356 逐位分解时, 获得 3, 5, 6 , 由s_3 = mi, s_5 = go, s_6 = ro 按此顺序连接而成的字符串 migoro 表示 w_1 。 创建一个输出
  • v_2 = 461 逐位分解时, 获得 4, 6, 1 , 由s_4 = yo, s_6 = ro, s_1 = i 按此顺序连接而成的字符串 yoroi 表示 w_2 。 创建一个输出
  • v_3 = 2 逐位分解时, 获得 2 , 由s_2 = ni 表示 w_3 。 创建一个输出
  • v_4 = 12 逐位分解时, 获得 1, 2 , 由s_1 = i, s_2 = ni 按此顺序连接而成的字符串 ini 表示 w_4 。 创建一个输出

此输入示例是一个数据集 请注意,不满足条件 1 。


入力例2

3 4
21 aaa
12 aaa
123 aaaaaa
13 aaaa

出力例2

a
aa
aaa

入力例3

2 3
12211 abcaaaaabcabc
2121 aaabcaaabc
222221 aaaaaaaaaaabc

出力例3

abc
aa

入力例4

2 1
12 abcab

出力例4

ab
cab