QOJ.ac

QOJ

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓

#15410. 防御距离

Statistiques

NWRRC 安全服务器对尝试向秘密隐藏题目提交解答的队伍进行最终的访问权限检查。

为了通过检查,队伍必须输入系统接受的三个密码 $s$、$t$ 和 $u$。每个密码必须是由最多 5000 个小写英文字母组成的非空字符串。

服务器的规则是公开的:

  • $s$ 和 $t$ 之间的距离应该等于 $a$。
  • $s$ 和 $u$ 之间的距离应该等于 $b$。
  • $t$ 和 $u$ 之间的距离应该等于 $c$。

两个字符串 $s_1$ 和 $s_2$ 之间的距离是将字符串 $s_1$ 转换为字符串 $s_2$ 所需的最少单字符操作(插入一个字符、删除一个字符或替换一个字符)次数。该度量也被称为编辑距离(Levenshtein distance)。

当且仅当满足所有上述条件时,服务器才会允许访问隐藏题目。你的目标是构造一组密码三元组以解锁隐藏题目,或者确定这是不可能的。

输入格式

唯一的一行包含三个整数 $a$、$b$ 和 $c$,表示每对密码之间要求的距离($0 \le a, b, c \le 1000$)。

输出格式

如果不存在具有所需属性的三个密码,则在唯一的一行中输出 No

否则,在第一行输出 Yes。然后在接下来的三行中分别输出密码 $s$、$t$ 和 $u$。每个密码应包含至少 1 个且最多 5000 个小写英文字母。

如果有多组满足要求的密码三元组,输出其中任意一组即可。

样例

输入样例 1

4 3 5

输出样例 1

Yes
icpc
nwrrc
itmo

输入样例 2

2 2 2

输出样例 2

Yes
aa
bb
cc

输入样例 3

0 0 1

输出样例 3

No

说明

在第一个测试样例中:

  • "icpc""nwrrc" 之间的距离为 4:"icpc" $\to$ "irpc" $\to$ "irrc" $\to$ "nrrc" $\to$ "nwrrc"
  • "icpc""itmo" 之间的距离为 3:"icpc" $\to$ "itpc" $\to$ "itpo" $\to$ "itmo"
  • "nwrrc""itmo" 之间的距离为 5:"nwrrc" $\to$ "wrrc" $\to$ "wrro" $\to$ "irro" $\to$ "itro" $\to$ "itmo"

在第二个测试样例中,每对密码之间的距离均为 2。

在第三个测试样例中,可以证明不存在具有所需属性的三个密码。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.