← 返回题目列表

Codeforces · 1949/D

D. 有趣还是可怕?

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

您正在设计一款新视频游戏。它有 $$$n$$$ 场景,玩家可以按任意顺序玩这些场景,但每个场景必须只玩一次。当玩家从一个场景切换到另一个场景时,游戏会显示一个专门制作的过渡视频,让人感觉这一切都是一个大故事的一部分。该视频是特定于一对场景的,但不限于它们的顺序,也就是说,从场景$$$a$$$切换到场景$$$b$$$时播放的视频与从场景$$$b$$$切换到场景$$$a$$$时播放的视频相同。因此,您需要创建 $$$\frac{n(n-1)}{2}$$$ 不同的过渡视频,每个视频对应一对可能的不同场景。

每个过渡视频可以是有趣的或可怕的。连续看太多搞笑视频或太多恐怖视频会很无聊。因此,您的目标是创建这样的视频:无论玩家以何种顺序处理场景,他们都不会连续看到超过 $$$\lceil \frac{3n}{4} \rceil$$$ 相同类型的过渡视频。

您已经对最多 $$$\lfloor \frac{n}{2} \rfloor$$$ 的过渡视频提出了想法,因此已经知道这些视频是有趣还是可怕。现在您需要为所有其他过渡视频选择有趣或恐怖,以满足上述要求。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 24$$$) — 游戏中的场景数量。

接下来的 $$$n$$$ 行描述了部分过渡视频计划。每行都包含 $$$n$$$ 字符。第$$$i$$$行的第$$$j$$$字符对应于第$$$i$$$场景和第$$$j$$$场景之间的过渡视频。如果相应的过渡视频很有趣,则为 F;如果相应的过渡视频很恐怖,则为 S;?如果相应的过渡视频仍未确定,或者。 如果$$$i=j$$$。

保证 $$$j$$$ 行的第 $$$i$$$ 字符和 $$$i$$$ 行的第 $$$j$$$ 字符对于所有 $$$i$$$ 和 $$$j$$$ 都是相同的。保证最多 $$$\lfloor \frac{n}{2} \rfloor$$$ ($$$n$$$ 除以 2,向下舍入)过渡视频已经确定,换句话说,输入中最多 $$$2\lfloor \frac{n}{2} \rfloor$$$ 字符将为 F 或 S。

输出

以与输入相同的格式打印描述完整过渡视频计划的 $$$n$$$ 行。每行都必须包含 $$$n$$$ 字符。如果相应的过渡视频很有趣,则第 $$$i$$$ 行的第 $$$j$$$ 个字符必须为 F;如果相应的过渡视频很恐怖,则必须为 S;否则。 如果$$$i=j$$$。

每个?输入中的字符必须替换为 F 或 S,并且输入中的所有其他字符必须保持不变。仍然必须认为,对于所有 $$$i$$$ 和 $$$j$$$,第 $$$j$$$ 行的第 $$$i$$$ 字符和第 $$$i$$$ 行的第 $$$j$$$ 字符是相同的。

对于 $$$n$$$ 场景的每个排列,必须满足按此顺序播放场景对应的过渡视频不连续有超过 $$$\lceil \frac{3n}{4} \rceil$$$ ($$$3n$$$ 除以 4,向上取整) 个相同类型的视频。

如果有多个解决方案,请打印其中任何一个。可以证明,对于满足该问题约束的所有输入,解总是存在。

示例

输入 #1

5
.?F??
?.???
F?.S?
??S.?
????.

输出 #1

.FFFF
F.FFF
FF.SF
FFS.F
FFFF.

输入 #2

12
.???????????
?.??????????
??.?????????
???.????????
????.???????
?????.??????
??????.?????
???????.????
????????.???
?????????.??
??????????.?
???????????.

输出 #2

.SSSFFSSSSFS
S.SFFSFSFFFS
SS.SFFFSSSFS
SFS.FFSSSSFS
FFFF.FFFFFSF
FSFFF.SFFSFF
SFFSFS.SSSFS
SSSSFFS.SSFS
SFSSFFSS.SFS
SFSSFSSSS.FS
FFFFSFFFFF.F
SSSSFFSSSSF.

注意

在第一个示例中:我们允许连续 $$$\lceil \frac{3\cdot 5}{4} \rceil=4$$$ 相同类型的过渡视频,但是对于 5 个场景的任何排列,玩家总共只会看到 4 个过渡视频,因此我们可以自由选择有趣或恐怖。我们仍然必须尊重已经选择的类型。

在第二个示例中:479001600 种可能的场景排列之一是 1、7、4、12、9、8、2、6、10、3、11、5。播放器将获得此排列的以下过渡视频序列:SSSSSSSSSFS。尽管该序列总共有 10 个可怕的过渡视频,但它连续只有 9 个可怕的过渡视频,这是允许的最大数量 ($$$\lceil \frac{3\cdot 12}{4} \rceil=9$$$)。