← 返回题目列表

Codeforces · 1903/E

E. 地理游戏

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

这是一个交互问题。

Theofanis 和他的妹妹正在玩以下游戏。

它们在 2D 平面中有 $$$n$$$ 个点和一个起点 $$$(s_x,s_y)$$$。每个玩家(从第一个玩家开始)选择之前未选择的 $$$n$$$ 点中的一个,并将前一个点(起点或由其他人选择的点)到新点(当前玩家选择的点)的欧几里得距离的平方添加到总和(最初为 $$$0$$$)中。

游戏在恰好 $$$n$$$ 步后结束(选择所有点后)。如果最后总和相等,则第一个玩家获胜。否则,第二个玩家获胜。

Theofanis 是一个非常好胜的人,他讨厌失败。因此,他要选择是先打还是后打。你能告诉他,该选择哪位选手,以及他应该如何打球才能击败他的妹妹吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。

每个测试用例的数据仅在所有先前测试用例的交互结束(游戏结束)后才可用。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — 点数。

每个测试用例的第二行包含两个整数 $$$s_x$$$, $$$s_y$$$ ($$$0 \le s_x, s_y \le 10^{9}$$$) — 起点的坐标。

两个或多个点可能具有相同的坐标。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^{9}$$$) — 第 $$$i$$$ 个点的坐标。

保证所有测试用例的$$$n$$$总和不超过$$$10^{5}$$$。

互动

对于每个测试用例,您应该首先输出您想要扮演的玩家(第一或第二)。

那么,你应该玩游戏了。当轮到你时,你应该输出你想要选择的点的索引$$$j$$$ ($$$1 \le j \le n$$$),当轮到其他玩家时,你应该读取他们选择的索引。

当所有轮次完成后,继续读取下一个测试用例的输入,或者结束程序(如果没有)。

如果您收到整数 $$$-1$$$ 而不是索引或有效值 $$$n$$$,则意味着您的程序在之前的测试用例中做出了无效的举动或输掉了游戏。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印玩家的选择或回合后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

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

黑客

要破解,请使用以下格式。

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — 点数。

每个测试用例的第二行包含两个整数 $$$s_x$$$, $$$s_y$$$ ($$$0 \le s_x, s_y \le 10^{9}$$$) — 起点的坐标。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^{9}$$$) — 第 $$$i$$$ 个点的坐标。

所有测试用例的 $$$n$$$ 总和不应超过 $$$10^{5}$$$。

示例

输入 #1

2
6
4 6
7 6
8 5
2 1
6 2
6 4
3 3

2

5

1
4
1 1
3 2
2 1
3 3
1 2


2

3

输出 #1

Second

4

6

3
First
1

4

注意

上面的例子并不一定展示最佳策略或选择正确的玩家。

在下图中,您可以看到每个玩家在第一个示例中所做的动作。第一个玩家是红色的,第二个玩家是黑色的。