CF1045F Shady Lady
题目描述
Ani 和 Borna 正在玩一个关于二元多项式的小游戏。这是一种特殊的多项式:所有的单项式都是固定的,但它们的系数都是空白,例如 $\_ xy + \_ x^4 y^7 + \_ x^8 y^3 + \ldots$。
Borna 将用正整数填补这些空白。他希望这个多项式是下有界的,也就是说,他的目标是确保存在一个实数 $M$,使得无论在任何点,多项式的值都大于 $M$。
Ani 很调皮,她希望让多项式无下界。除了偷走 Borna 的心,她还可以偷走多项式中的部分项。不过,Ani 只是个小偷,她最多只能在 Borna 填空之前偷走一个单项式。
如果 Ani 和 Borna 都采取最优策略,谁会获胜?
输入格式
第一行包含一个正整数 $N$($2 \leq N \leq 200\,000$),表示初始特殊多项式中的项数。
接下来的 $N$ 行,每行描述一个单项式:第 $k$ 行包含两个用空格分隔的整数 $a_k$ 和 $b_k$($0 \leq a_k, b_k \leq 10^9$),表示初始多项式中有一项 $\_ x^{a_k} y^{b_k}$。保证对于 $k \neq l$,要么 $a_k \neq a_l$,要么 $b_k \neq b_l$。
输出格式
如果无论 Ani 偷哪一项,Borna 都能选择系数使得最终多项式下有界,则输出 Borna。否则,输出 Ani。
不要输出引号。
说明/提示
在第一个样例中,初始多项式为 $\_xy + \_x^2 + \_y^2$。如果 Ani 偷走了 $\_y^2$ 项,Borna 剩下 $\_xy + \_x^2$。无论空白处填什么正整数,当 $y \rightarrow -\infty$ 且 $x := 1$ 时,整个表达式趋于负无穷。
在第二个样例中,初始多项式为 $\_1 + \_x + \_x^2 + \_x^8$。可以验证,无论 Ani 偷哪一项,Borna 都能获胜。
由 ChatGPT 4.1 翻译