CF1045F.Shady Lady

NOI/NOI+/CTSC

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Ani and Borna are playing a short game on a two-variable polynomial. It's a special kind of a polynomial: the monomials are fixed, but all of its coefficients are fill-in-the-blanks dashes, e.g. $$ \_ xy + \_ x^4 y^7 + \_ x^8 y^3 + \ldots $$

Borna will fill in the blanks with positive integers. He wants the polynomial to be bounded from below, i.e. his goal is to make sure there exists a real number MM such that the value of the polynomial at any point is greater than MM.

Ani is mischievous, and wants the polynomial to be unbounded. Along with stealing Borna's heart, she can also steal parts of polynomials. Ani is only a petty kind of thief, though: she can only steal at most one monomial from the polynomial before Borna fills in the blanks.

If Ani and Borna play their only moves optimally, who wins?

阿尼和博尔纳正在玩一个关于双变量多项式的简短游戏。这是一种特殊的多项式:其中单项式是固定的,但所有系数都是待填空的横线,例如

_ xy+_ x4y7+_ x8y3+…\_\, xy + \_\, x^4 y^7 + \_\, x^8 y^3 + \ldots

博尔纳将用正整数填入这些横线。他希望该多项式有下界,即:他的目标是确保存在某个实数 MM,使得该多项式在任意点处的取值均大于 MM。

阿尼则顽皮捣蛋,希望该多项式无界。除了偷走博尔纳的心之外,她还能偷走多项式的一部分。不过阿尼只是个小偷:在博尔纳填空之前,她最多只能从多项式中偷走一个单项式。

若阿尼与博尔纳均以最优策略进行各自唯一的一次操作,谁将获胜?

输入格式

The first line contains a positive integer NN (2≤N≤200 000)(2 \leq N \leq 200\, 000), denoting the number of the terms in the starting special polynomial.

Each of the following NN lines contains a description of a monomial: the kk-th line contains two **space**-separated integers aka_k and bkb_k (0≤ak,bk≤109(0 \leq a_k, b_k \leq 10^9) which mean the starting polynomial has the term _xakybk\_ x^{a_k} y^{b_k}. It is guaranteed that for k≠lk \neq l, either ak≠ala_k \neq a_l or bk≠blb_k \neq b_l.

第一行包含一个正整数 NN(2≤N≤200 0002 \leq N \leq 200\, 000),表示初始特殊多项式中项的个数。

接下来的 NN 行每行描述一个单项式:第 kk 行包含两个用空格分隔的整数 aka_k 和 bkb_k(0≤ak,bk≤1090 \leq a_k, b_k \leq 10^9),表示初始多项式中包含项 _xakybk\_ x^{a_k} y^{b_k}。保证对任意 k≠lk \neq l,均有 ak≠ala_k \neq a_l 或 bk≠blb_k \neq b_l。

输出格式

If Borna can always choose the coefficients such that the resulting polynomial is bounded from below, regardless of what monomial Ani steals, output "Borna". Else, output "Ani".

You shouldn't output the quotation marks.

如果无论Ani偷走哪一个单项式,Borna总能选择系数,使得所得多项式有下界,则输出 Borna;否则输出 Ani。
你不需要输出引号。

输入输出样例

  • 输入#1

    3
    1 1
    2 0
    0 2

    输出#1

    Ani
  • 输入#2

    4
    0 0
    0 1
    0 2
    0 8

    输出#2

    Borna

说明/提示

In the first sample, the initial polynomial is _xy+_x2+_y2\_xy+ \_x^2 + \_y^2. If Ani steals the _y2\_y^2 term, Borna is left with _xy+_x2\_xy+\_x^2. Whatever positive integers are written on the blanks, y→−∞y \rightarrow -\infty and x:=1x := 1 makes the whole expression go to negative infinity.

In the second sample, the initial polynomial is _1+_x+_x2+_x8\_1 + \_x + \_x^2 + \_x^8. One can check that no matter what term Ani steals, Borna can always win.

在第一个样例中,初始多项式为 _xy+_x2+_y2\_xy+ \_x^2 + \_y^2。若 Ani 偷走了 _y2\_y^2 项,则 Borna 剩余的表达式为 _xy+_x2\_xy+\_x^2。无论空白处填入怎样的正整数,取 y→−∞y \rightarrow -\infty 且 x:=1x := 1 都会使整个表达式趋于负无穷。

在第二个样例中,初始多项式为 _1+_x+_x2+_x8\_1 + \_x + \_x^2 + \_x^8。可以验证:无论 Ani 偷走哪一项,Borna 总能获胜。

输入解题思路,AI测评打分。不知道怎么写?

首页