← 返回题目列表

Codeforces · 388/B

B. 狐狸和最小路径

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

Fox Ciel 想要为编程竞赛编写一个任务。任务是:“给你一个有 n 个顶点的简单无向图。它的每条边都有单位长度。你应该计算顶点 1 和顶点 2 之间的最短路径的数量。”

和一些作家一样,她想用一些特定的输出来做一个例子:例如,她的生日或她男朋友的号码。你能帮她做一个答案恰好等于 k ​​的测试用例吗?

输入

第一行包含一个整数 k (1 ≤ k ≤ 109)。

输出

您应该输出一个具有 n 个顶点的图 G (2 ≤ n ≤ 1000)。图的顶点 1 和顶点 2 之间必须恰好有 k 条最短路径。

第一行必须包含整数 n。然后必须遵循 n 行 n 列的邻接矩阵 G。矩阵的每个元素必须是“N”或“Y”。如果 Gij 为“Y”,则图 G 具有连接顶点 i 和顶点 j 的边。考虑图的顶点从 1 到 n 编号。

图必须是无向且简单的:Gii = 'N' 且 Gij = Gji 必须成立。并且顶点1和顶点2之间必须至少有一条路径。保证答案存在。如果有多个正确答案,则可以输出其中任何一个。

示例

输入 #1

2

输出 #1

4
NNYY
NNYY
YYNN
YYNN

输入 #2

9

输出 #2

8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN

输入 #3

1

输出 #3

2
NY
YN

注意

在第一个示例中,有 2 条最短路径:1-3-2 和 1-4-2。

在第二个示例中,有 9 条最短路径:1-3-6-2、1-3-7-2、1-3-8-2、1-4-6-2、1-4-7-2、1-4-8-2、1-5-6-2、1-5-7-2、1-5-8-2。