QOJ.ac

QOJ

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓

#17963. 棋盘游戏

الإحصائيات

Jeyeon 和 Deokin 沉迷于解题,并且永远不想退休。他们开发了一款新的棋盘游戏,并决定在完全分析清楚这款游戏之前绝不退休。

游戏由 $K$ 个棋盘和 $K$ 个棋子组成。第 $i$($i = 1, \dots, K$)个棋盘是一个大小为 $N_i \times M_i$ 的网格。对于每个棋盘,有两条栅栏构成边界。栅栏是长度为 $N_i + M_i$ 的路径,从左上角顶点开始,到右下角顶点结束,且只能通过向右(R)或向下(D)移动长度为 1 的步数来描绘。除了左上角和右下角顶点外,这两条栅栏不会相交。

例如,考虑 $N_i = 5, M_i = 4$ 的情况。在情况 (a) 中,两条路径 RRDRDDDRDDDRRDDDRR 除了左上角和右下角顶点外没有交点,因此这是一个合法的输入。另一方面,在情况 (b) 中,所选的两条栅栏 RDRDRDRDDDDRRDDDRR 在除了左上角和右下角之外的顶点相交,因此这是不合法的输入。在情况 (c) 中,其中一条栅栏无法仅通过向右和向下移动来描绘,因此它也是不合法的输入。

游戏开始时有 $K$ 个棋盘,每个棋盘上有两条栅栏。每个棋盘上都有一个棋子,初始放置在左上角的方格中。Jeyeon 先手,然后两人轮流操作。在 Jeyeon 的回合中,Jeyeon 必须选择 $K$ 个棋子中的一个,并将其移动到当前方格正右侧的方格中;在 Deokin 的回合中,Deokin 必须选择 $K$ 个棋子中的一个,并将其移动到当前方格正下方的方格中。不允许将棋子移动到跨越栅栏的位置。在自己的回合中无法进行合法移动的玩家输掉游戏。

你是一个热衷于解题的人,并且极度渴望获胜。然而,由于 Jeyeon 和 Deokin 非常强大,你永远无法击败他们。但是,如果你能完美地分析这个游戏,也许他们会考虑退休?

给定 $K$ 个棋盘,请确定在双方都采取最优策略的情况下,游戏的获胜者。

输入格式

第一行包含一个整数 $K$($1 \le K$)。

接下来的 $3K$ 行按顺序包含第 $i = 1, 2, \dots, K$ 个网格的信息。

每个网格由三行表示。第一行包含两个整数 $N_i, M_i$。接下来的两行包含每条栅栏的方向序列,这是一个长度为 $N_i + M_i$ 且仅由 RD 组成的字符串($1 \le N_i, 1 \le M_i$)。

$N_i + M_i$ 的总和不超过 $500\,000$。

输出格式

如果 Jeyeon(先手)获胜,输出 First。如果 Deokin(后手)获胜,输出 Second

样例

输入样例 1

2
3 2
RRDDD
DRDDR
1 2
DRR
RRD

输出样例 1

First

输入样例 2

2
2 2
DRDR
RRDD
4 5
RDRDDRRRD
DDDRDRRRR

输出样例 2

Second

说明

样例 1 的图示。

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.