← 返回题目列表

AtCoder · xmascon18_c

C. 组合N

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

配点: 100 点

狐狸:“由于棘手的情况,我真的非常想现在就得到帕斯卡三角形呀。”

兔子:“我很久以前写过一个。”

問題文

从前,兔子想要写帕斯卡三角形的 N 行。从上面开始 i 段目 (0 \le i < N) 从左开始 j 番目 (0 \le j \le i所写的值记为 C[i][j] 。兔子试图按照以下程序计算每个 C[i][j] 的值

for i = 0 to N - 1:
    C[i][0] = C[i][i] = 1
    for j = 1 to i - 1:
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

,但(在上述伪代码中第 4 行的)加法刚好 1 次出错,结果变成比正确和更大的整数。

而且,经过多年,兔子写下的一些整数消失了。

当表示兔子写的三角形信息的整数 A_{i,j} (0 \le i < N,0 \le j \le i)。

  • A_{i,j} = 0 时,从三角形上方开始的 i 行,第 j 个写下的整数已经消失,无法知道。
  • A_{i,j} \ne 0 时,从三角形上方开始的 i 行,第 j 第 A_{i,j} 。

个写下的整数是 (i, j) 兔子在(哪个 C[i][j] 时是否加法错误。但是,如果可能的 (i, j) 有多个,或者有错误而不存在任何可能的 (i, j) ,请报告这一情况。按照

制約

  • 1 \le N \le 500.
  • 0 \le A_{i,j} \le 10^9.
  • i = 0, 1, \ldots, N - 1 反对 A_{i,0} = A_{i,i} = 1.

部分点

  • N \le 50 的数据集,20 点。 如果所有满足
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 80 点。 如果所有满足

入力

N
A_{0,0}
A_{1,0} A_{1,1}
\vdots
A_{N-1,0} A_{N-1,1} \cdots A_{N-1,N-1}

出力

兔子加法错了 (i, j) 该值应乘以 i, j 的顺序输出。但是,如果可能的 (i, j) 有多个,则输出 AMBIGUOUS ,如果不存在任何,则输出 IMPOSSIBLE 。


入力例 1

6
1
1 1
1 0 1
1 3 0 1
1 0 7 0 1
1 0 11 0 6 1

出力例 1

3 2

。在这种情况下,可以认为整数消失前兔子写的三角形如下。计算C[3][2] 时,错误地将 2 + 1 作为 4 ,由于(i, j) = (3, 2) 。 你只需要砍掉 

1
1 1
1 2 1
1 3 4 1
1 4 7 5 1
1 5 11 12 6 1

入力例 2

4
1
1 1
1 0 1
1 0 0 1

出力例 2

AMBIGUOUS

加法的部分全部消失,因此任何位置都有可能出错。


入力例 3

4
1
1 1
1 0 1
1 4 5 1

出力例 3

IMPOSSIBLE