兄妹 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$ 个顶点的坐标,该多边形代表披萨的初始形状。
保证多边形是严格凸的,且顶点按逆时针顺序给出。
交互
首先,你需要打印一行,内容为字符串 Alberto 或 Beatrice,表示你将帮助哪一方获胜。
然后,在接下来的 $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,这小于整个披萨面积的一半。此交互示例中参赛者和裁判的操作可能并非最优。过程如下图所示: