← 返回题目列表

Codeforces · 1384/A

A. 常见前缀

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

两个字符串 $$$s = s_1 s_2 \ldots s_n$$$ 和 $$$t = t_1 t_2 \ldots t_m$$$ 的最长公共前缀的长度定义为最大整数 $$$k$$$ ($$$0 \le k \le min(n,m)$$$) 使得 $$$s_1 s_2 \ldots s_k$$$ 等于$$$t_1 t_2 \ldots t_k$$$。

Koa 考拉最初有 $$$n+1$$$ 字符串 $$$s_1, s_2, \dots, s_{n+1}$$$。

对于每个 $$$i$$$ ($$$1 \le i \le n$$$),她计算了 $$$a_i$$$ — $$$s_i$$$ 和 $$$s_{i+1}$$$ 的最长公共前缀的长度。

几天后,Koa 找到了这些数字,但她不记得这些字符串了。

所以 Koa 想找到一些字符串 $$$s_1, s_2, \dots, s_{n+1}$$$ ,它们会生成数字 $$$a_1, a_2, \dots, a_n$$$。你能帮助她吗?

如果有很多答案,请打印任何答案。我们可以证明对于给定的约束,答案总是存在。

输入

每个测试包含多个测试用例。第一行包含 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 列表 $$$a$$$ 中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 50$$$) - $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$100$$$。

输出

对于每个测试用例:

输出 $$$n+1$$$ 行。在第 $$$i$$$ 行中打印字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 200$$$),由小写拉丁字母组成。字符串 $$$s_i$$$ 和 $$$s_{i+1}$$$ 的最长公共前缀的长度必须等于 $$$a_i$$$。

如果有很多答案,请打印任何答案。我们可以证明对于给定的约束,答案总是存在。

示例

输入 #1

4
4
1 2 4 2
2
5 3
3
1 3 1
3
0 0 0

输出 #1

aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems

注意

在 $$$1$$$-st 测试用例中,可能的答案之一是 $$$s = [aeren, ari, arousal, around, ari]$$$。

最长公共前缀的长度为:

- $$$\color{red}{a}eren$$$ 和 $$$\color{red}{a}ri$$$ $$$\rightarrow 1$$$ 之间
- $$$\color{red}{ar}i$$$ 和 $$$\color{red}{ar}ousal$$$ $$$\rightarrow 2$$$ 之间
- $$$\color{red}{arou}sal$$$ 和 $$$\color{red}{arou}nd$$$ $$$\rightarrow 4$$$ 之间
- $$$\color{red}{ar}ound$$$ 和 $$$\color{red}{ar}i$$$ $$$\rightarrow 2$$$ 之间