C - CombinatioN Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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