← 返回题目列表

AtCoder · tupc2024_r

R. 括号游戏

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

配点 : {100} 点

致环球杯参赛者

当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了

問題文

(, ), ? 组成长度为偶数的字符串 S 。 对于

青叶小姐和广濑先生进行游戏。青叶小姐先手, S 至 该值是 ? ,就交替进行以下操作。 是

  • S 可以得到第 ? 的字符 当 1 选择( 或 至少 ) 。

S 减去 ? 消失时, 如果S 是正确的括号序列,则青叶女士获胜,否则广濑先生获胜。

请判定当双方为自己获胜而采取最佳行动时,谁会获胜。

T 测试用例,因此请逐一回答。

正确的括号序列是 满足以下任一条件的字符串定义为正确的括号序列。
  • 空文字列
  • 一些正确的括号序列 S 存在, 由(, S, ) 按此顺序连接而成的字符串
  • 有效的非空括号序列 S, T 存在, 由 S,T 按此顺序连接而成的字符串

制約

  • 1\leq T\leq 10^5
  • 2\leq |S|\leq 10^6
  • S 是 您也可以写 (, ), ? 组成长度为偶数的字符串
  • 包含在一个输入文件中的 |S| 的总和为 10^6 以下
  • T 是一个整数

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出。 打印

S

出力

T 行。i 在线 i 第几个测试用例,如果青叶先生获胜 First 如果广濑先生获胜 Second 。


入力例 1

3
(???
(()())
??????

出力例 1

First
First
Second

1 关于第几个测试用例,游戏的进行可以考虑如下情形。

  • 开始 S 是 您也可以写 (??? 。
  • 青叶先生 4 第几个字符 ? 该值应乘以 ) 。S 是 您也可以写 (??) 。
  • 广濑先生 2 第几个字符 ? 该值应乘以 ) 。S 是 您也可以写 ()?) 。
  • 青叶先生 3 第几个字符 ? 该值应乘以 ( 。S 是 您也可以写 ()() 。
  • S 至 该值是 ? 因为已经没有了,所以操作结束。S 是正确的括号序列,因此青叶先生获胜。

1 在第几个测试用例里,无论广濑先生如何行动,青叶先生都可以获胜。