読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ゆらふなセンパイお誕生日コンテスト C - パスカルの三角形

「やられた!」と思った問題。こんなんがCODE FESTIVALの決勝でも出るんだなあ…。

問題

yurahuna2016.contest.atcoder.jp

元問題はこちら

code-festival-2014-final-open.contest.atcoder.jp

与えられる整数Aがパスカルの三角形に含まれるなら、その段数・行数を出力せよ。含まれないなら'-1 -1'と出力せよ。

制約

 1 \leq A \leq 10^9

解法

※この問題はネタバレ前に一度自分で考えてみることを強くおすすめします。解法まで行を開けておくので、まだ解いてない!という方はリターン→→































~~~ここから解法~~~

パスカルの三角形を作るとして、どこまで作ればいいのだろうか? 構築に O(N^2)かかるけどAはそれで間に合う範囲にあるのか??

などと考える必要はなかった。なぜなら、


 {}_A C_{1} = A


つまり、Aは必ずパスカルの三角形に存在し、答えは O(1)で求まるわけです。

気をつけるところがあるとすれば、問題は1-indexだということくらい。さすがにpythonで解いた。

所要時間10:43

a = int(input())
print(a + 1, 1 + 1)

こういう問題、yukicoderで慣れたつもりでいたものの、いざ出されるとやっぱりすぐにはわからない。