QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100 Interactive

#5649. 菠菜披萨

Statistics

兄妹 Alberto 和 Beatrice 需要一起吃一份菠菜披萨。然而,他们都不喜欢菠菜,因此两人都想尽可能少吃。

披萨的形状是一个严格凸多边形,其 $n$ 个顶点位于平面上的整数坐标 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ 处。

兄妹俩决定按以下方式吃披萨:从 Alberto 开始轮流进行,每人选择剩余披萨的一个顶点,并吃掉由该顶点及其两个相邻边所构成的三角形。这样,在最初的 $n-3$ 次操作后,披萨的顶点数会减少。游戏在第 $n-2$ 次操作后结束,此时披萨已被全部吃完。

假设 Alberto 和 Beatrice 在选择要吃的披萨块时都采取最优策略,哪一方能够保证吃掉的披萨不超过总面积的一半?你需要找出有策略做到这一点的一方,并帮助他们适当地选择披萨块。注意,如果双方都采取最优策略,两人最终可能恰好各吃掉一半面积。

输入格式

第一行包含一个整数 $n$ ($4 \le n \le 100$),表示顶点数。

接下来的 $n$ 行,每行包含两个整数 $x_i$ 和 $y_i$ ($-10^6 \le x_i, y_i \le 10^6$),表示多边形的第 $i$ 个顶点的坐标,该多边形代表披萨的初始形状。

保证多边形是严格凸的,且顶点按逆时针顺序给出。

交互

首先,你需要打印一行,内容为字符串 AlbertoBeatrice,表示你将帮助哪一方获胜。

然后,在接下来的 $n-2$ 个回合中,你将与裁判交替选择披萨块并将其移除。如果你选择帮助 Alberto,则由你先开始;如果你选择帮助 Beatrice,则由裁判先开始。

  • 当轮到你时,打印一行,包含一个尚未被选择过的整数 $p$ ($1 \le p \le n$),表示你想要吃掉由顶点 $(x_p, y_p)$ 确定的披萨块。
  • 当轮到裁判时,读取一个整数 $q$ ($1 \le q \le n$),表示对方吃掉了由顶点 $(x_q, y_q)$ 确定的披萨块。保证 $q$ 之前未被选择过。

如果你的交互格式错误,交互器将立即终止,你的程序将收到 WRONG-ANSWER 判决。否则,如果游戏结束时你所帮助的玩家吃掉的披萨不超过总面积的一半,你将收到 CORRECT,否则收到 WRONG-ANSWER

打印一行后,请务必换行并刷新输出。否则,你将收到 TIMELIMIT 判决。刷新输出的方法如下:

  • C 语言:fflush(stdout);
  • C++:fflush(stdout);cout << flush;cout.flush();
  • Java 和 Kotlin:System.out.flush();
  • Python:sys.stdout.flush();

样例

样例输入 1

4
0 0
6 1
5 3
1 4

样例输出 1

-

说明 1

披萨的总面积为 15。Alberto 可以通过吃掉顶点 2 附近的披萨块(面积为 6.5)或顶点 3 附近的披萨块(面积为 3.5)来吃掉少于一半的披萨。

样例输入 2

6
0 0
2 0
3 2
2 4
0 4
-1 2

样例输出 2

-

说明 2

可以证明,如果双方都采取最优策略,两人最终将恰好各吃掉一半的披萨。因此,选择帮助 Alberto 或 Beatrice 均可。

样例输入 3

7
0 0
2 0
5 2
4 5
1 5
-1 4
-1 2

样例输出 3

-

说明 3

可以证明,只有 Beatrice 有策略保证吃掉不超过一半的披萨。以下是一个有效交互的示例(读取输入后):

参赛者 裁判 说明
Beatrice 参赛者将帮助 Beatrice
7 Alberto 吃掉顶点 6, 7, 1 构成的三角形,面积为 1
2 Beatrice 吃掉顶点 1, 2, 3 构成的三角形,面积为 2
5 Alberto 吃掉顶点 4, 5, 6 构成的三角形,面积为 1.5
4 Beatrice 吃掉顶点 3, 4, 6 构成的三角形,面积为 8
6 Alberto 吃掉顶点 3, 6, 1 构成的三角形,面积为 11

Alberto 吃掉的总面积为 13.5,Beatrice 吃掉的总面积为 10,这小于整个披萨面积的一半。此交互示例中参赛者和裁判的操作可能并非最优。过程如下图所示:

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.