QOJ.ac

QOJ

時間限制: 5 s 記憶體限制: 512 MB 總分: 100

#8090. 修建老匠

统计

Gurdurr 经常在建筑工地上帮忙。别担心,Gurdurr 在工作中受到了很好的对待——它们有免费的食物,并且被允许频繁地从工作中休息。在这些休息时间里,它们喜欢玩它们最喜欢的游戏——叠叠乐(Jenga)。由于它们非常强壮,它们用沉重的钢块玩叠叠乐——这是它们从不离身的东西。它们的叠叠乐有以下规则:

塔由 $n$ 层积木组成。每一层由三根长钢块组成。每一层的积木彼此平行放置。相邻两层的积木相互垂直。游戏开始时,有些积木可能已经缺失。两名玩家轮流进行移动。在一次移动中,玩家必须选择一个积木并将其从塔中移除,前提是移除后塔仍然保持稳定。如果满足以下所有条件,则塔是稳定的:

  • 每一层至少包含一个积木。
  • 如果一层恰好包含一个积木,那么它必须是中间的那一个。
  • 不存在相邻的两层都只包含一个积木的情况。

无法进行任何移动的玩家输掉比赛。Gurdurr 非常擅长这个游戏,所以你可以假设它们采取最优策略。给定塔的初始状态,可能已经移除了一些积木。保证初始塔是稳定的。你的任务是确定哪个玩家将赢得这场游戏。

请注意,在这个版本的叠叠乐中,玩家不会把积木放到塔顶。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 30\,000$),表示测试用例的数量。接下来的 $t$ 个部分描述每个测试用例。

每个部分以一行包含一个整数 $n$ ($1 \le n \le 20$) 开始,表示塔的层数。然后有 $n$ 行,第 $i$ 行描述从塔顶开始的第 $i$ 层。

这些行中的每一行都包含一个由恰好三个字符组成的字符串。每个字符要么是 ‘I’,要么是 ‘.’。如果第 $i$ 行的第 $j$ 个字符是 ‘I’,则表示从塔顶开始的第 $i$ 层中的第 $j$ 个积木尚未被移除。如果该字符是 ‘.’,则表示该积木已被移除。我们假设每一层积木的编号是自然的,即第二个积木是中间的,第一个和第三个积木位于一层的外侧。

保证所有描述的塔都是稳定的。

输出格式

对于每个测试用例,输出一行,包含一个字符串 FirstSecond,取决于哪个玩家将获胜。

样例

样例输入 1

5
1
III
1
I.I
1
.I.
1
.II
2
III
III

样例输出 1

First
Second
Second
First
First

样例输入 2

1
3
II.
.II
III

样例输出 2

Second

说明

注意,在第一个样例测试的第二个和第三个测试用例中,无法进行任何移动,因此先手玩家立即输掉比赛。

这里是第二个样例测试中的塔,以及两只拿着它们自己金属梁(不是从塔中取出的)的 Gurdurr:

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#198EditorialOpen题解jiangly2025-12-13 00:05:51View

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.