配点: 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