SECON 2017 Online CTF Run me!(Programming, 100pt)
問題文
Run me! ----- RunMe.py import sys sys.setrecursionlimit(99999) def f(n): return n if n < 2 else f(n-2) + f(n-1) print "SECCON{" + str(f(11011))[:32] + "}" -----
11011番目のフィボナッチ数列を計算するプログラムですが、再帰なので自明にスタックオーバーフローします。
なので、動的計画法で書き直します。
import sys sys.setrecursionlimit(99999) fib = [0] * 99999 fib[1] = 1 fib[2] = 1 for i in range(3, 11111): fib[i] = fib[i-1] + fib[i-2] print "SECCON{" + str(fib[11011])[:32] + "}"
これで実行できました。
一時変数を全部配列で持ってしまっていますが、本来はラスト2つだけ持てば十分ですね。
感想
完全に競技プログラミング系の問題ですね。
こういうのも出るのか、、、と思いました。