Code festival 2014 決勝 D パスカルの三角形 python 3

2020/7/9 2022/5/17 競技プログラミング

問題:https://atcoder.jp/contests/code-festival-2014-final/tasks/code_festival_final_d

かなりのひっかけ問題で、私はまんまと引っかかってしまいました。よくできた問題だと思います。

コード例

たったこれだけのコードでACできます。

N=int(input())
print(N+1,2)

まともにパスカルの三角形の各項を求めていては、Nが10^9なので到底間に合いません。実はパスカルの三角形を見ていくと、下記のように各列の2番目の項には自然数の列が出来上がります。

問題文では「存在しない場合は-1 -1を出力せよ」と書いてあり、あたかも存在しない場合があるかのように書かれていますが、パスカルの三角形の性質上そのようなことはなく、必ず登場します。またパスカルの三角形には同じ数字が複数回現れる可能性がありますが、問題文ではパスカルの三角形に登場する限り行と列の番号が2*10^9以内であれば、どの場所を回答しても良いことになっています。

なので、N＋1行目の2番目に必ずNが現れる性質のため、上記のようなコードでACできました。

ちなみに「存在しない場合は-1 -1を出力せよ」のように書かれている問題のうち、サンプルケースで実際に「-1 -1」の実例が示されていない問題についてはひっかけである可能性が否定できないので疑ってかかりましょう。

なお、真面目にパスカルの三角形を出力するコードは以下の記事で扱っています。