← 返回题目列表

Codeforces · 1839/E

E. 减少游戏

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

这是一个交互问题。

考虑以下两个玩家的游戏:

- 最初,黑板上写着一个长度为 $$$n$$$ 的整数数组 $$$a_1, a_2, \ldots, a_n$$$。
- 游戏由回合组成。在每一轮中,都会发生以下情况:第一个玩家选择任意 $$$i$$$,使得 $$$a_i \gt 0$$$。如果没有这样的$$$i$$$,则第一个玩家输掉游戏(第二个玩家获胜)并且游戏结束。 第二个玩家选择任何 $$$j \neq i$$$ 使得 $$$a_j \gt 0$$$。如果没有这样的$$$j$$$,则第二个玩家输掉游戏(第一个玩家获胜)并且游戏结束。 令 $$$d = \min(a_i, a_j)$$$。 $$$a_i$$$和$$$a_j$$$的值同时减少$$$d$$$,然后下一轮开始。

可以证明,游戏总是在有限轮数后结束。

你必须选择你要为哪位玩家玩(第一或第二)并赢得比赛。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300$$$) — 数组 $$$a$$$。

互动

读取 $$$n$$$ 和数组 $$$a$$$ 后开始交互。

您应该通过打印一行来开始交互,其中包含“First”或“Second”,代表您选择的玩家。

每轮都会发生以下情况:

- 如果您作为第一个玩家玩,您应该在单独的行上打印一个整数 $$$i$$$ ($$$1 \le i \le n$$$)。之后,您应该读取写在单独一行上的单个整数 $$$j$$$ ($$$-1 \le j \le n$$$)。如果 $$$j = -1$$$,那么您的举动不正确。在这种情况下,你的程序应该立即终止。如果 $$$j = 0$$$,那么第二个玩家无法做出正确的动作,你就赢得了游戏。在这种情况下,你的程序也应该立即终止。否则 $$$j$$$ 等于第二个玩家选择的索引,你应该进入下一轮。
- 如果您作为第二个玩家玩,您应该读取写在单独一行上的单个整数 $$$i$$$ ($$$-1 \le i \le n$$$)。如果 $$$i = -1$$$,那么您在上一轮中做出了错误的动作(这不会在第一轮中发生)。在这种情况下,你的程序应该立即终止。如果 $$$i = 0$$$,那么第一个玩家无法做出正确的动作,你就赢得了游戏。在这种情况下,你的程序也应该立即终止。否则 $$$i$$$ 等于第一个玩家选择的索引。在这种情况下,您应该在单独的行上写入单个整数 $$$j$$$ ($$$1 \le j \le n$$$) 并继续下一轮。

打印 $$$i$$$ 或 $$$j$$$ 后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

在此问题中,黑客被禁用。

示例

输入 #1

4
10 4 6 3


3

1

0

输出 #1

First
1

2

4

输入 #2

6
4 5 5 11 3 2

2

5

4

6

1

0

输出 #2

Second 

4

4

3

1

3

注意

在第一个示例中 $$$n = 4$$$ 且数组 $$$a$$$ 为 $$$[\, 10, 4, 6, 3 \,]$$$。游戏进行如下:

- 读取数组 $$$a$$$ 后,参赛者的程序选择作为第一个玩家玩并打印“First”。
- 第一轮:第一个玩家选择$$$i = 1$$$,第二个玩家选择$$$j = 3$$$。 $$$d = \min(a_1, a_3) = \min(10, 6) = 6$$$ 被计算。元素 $$$a_1$$$ 和 $$$a_3$$$ 减少 $$$6$$$。数组 $$$a$$$ 等于 $$$[\, 4, 4, 0, 3 \,]$$$。
- 第二轮:第一个玩家选择$$$i = 2$$$,第二个玩家选择$$$j = 1$$$。 $$$d = \min(a_2, a_1) = \min(4, 4) = 4$$$ 被计算。元素 $$$a_2$$$ 和 $$$a_1$$$ 减少 $$$4$$$。数组 $$$a$$$ 等于 $$$[\, 0, 0, 0, 3 \,]$$$。
- 第三轮:第一位玩家选择$$$i = 4$$$。不存在 $$$j \neq 4$$$ 使得 $$$a_j > 0$$$,因此第二个玩家无法做出正确的动作,而第一个玩家获胜。陪审团的程序打印 $$$j = 0$$$。读完后,参赛者的程序终止。

在第二个示例中 $$$n = 6$$$ 且数组 $$$a$$$ 为 $$$[\, 4, 5, 5, 11, 3, 2 \,]$$$。游戏进行如下:

- 参赛者的程序选择作为第二个玩家进行比赛并打印“Second”。
- 第一轮:$$$i = 2$$$、$$$j = 4$$$、$$$a = [\, 4, 0, 5, 6, 3, 2 \,]$$$。
- 第二轮:$$$i = 5$$$、$$$j = 4$$$、$$$a = [\, 4, 0, 5, 3, 0, 2 \,]$$$。
- 第三轮:$$$i = 4$$$、$$$j = 3$$$、$$$a = [\, 4, 0, 2, 0, 0, 2 \,]$$$。
- 第四轮:$$$i = 6$$$、$$$j = 1$$$、$$$a = [\, 2, 0, 2, 0, 0, 0 \,]$$$。
- 第五轮:$$$i = 1$$$、$$$j = 3$$$、$$$a = [\, 0, 0, 0, 0, 0, 0 \,]$$$。
- 第六轮:第一个玩家无法做出正确的动作,第二个玩家获胜。陪审团的程序打印 $$$i = 0$$$。读完后,参赛者的程序终止。

请注意,示例交互包含额外的空行,以便更容易阅读。真正的交互不包含任何空行,您也不应该打印任何额外的空行。