結果

問題 No.657 テトラナッチ数列 Easy
ユーザー twkmathtwkmath
提出日時 2018-03-11 19:26:04
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
MLE  
実行時間 -
コード長 1,078 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 817,840 KB
最終ジャッジ日時 2024-10-15 00:23:17
合計ジャッジ時間 2,963 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
10,880 KB
testcase_01 AC 28 ms
10,880 KB
testcase_02 AC 27 ms
10,752 KB
testcase_03 AC 27 ms
10,880 KB
testcase_04 MLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def tetra_nacci(k, t):

	def calc(i):
		while True:
			if i in t.keys():
				return t[i]
			elif i-1 in t.keys():
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			elif i-2 in t.keys():
				t[i-1] = t[i-2]+t[i-3]+t[i-4]+t[i-5]
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			elif i-3 in t.keys():
				t[i-2] = t[i-3]+t[i-4]+t[i-5]+t[i-6]
				t[i-1] = t[i-2]+t[i-3]+t[i-4]+t[i-5]
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			elif i-4 in t.keys():
				t[i-3] = t[i-4]+t[i-5]+t[i-6]+t[i-7]
				t[i-2] = t[i-3]+t[i-4]+t[i-5]+t[i-6]
				t[i-1] = t[i-2]+t[i-3]+t[i-4]+t[i-5]
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			calc(i-4)

	if k in t:
		return t
	else:
		t[k] = calc(k)
		return t

q = int(input())
n_lst = [0]*q
for i in range(q):
	n_lst[i] = int(input())

t_dct = {-3:0, -2:0, -1:0, 0:0, 1:0, 2:0, 3:0, 4:1}
for i in range(q):
	k_lst = sorted(t_dct.keys())
	while k_lst[-1] + 1000 < n_lst[i]:
		t_dct = tetra_nacci(k_lst[-1]+1000, t_dct)
		k_lst = sorted(t_dct.keys())
	t_dct = tetra_nacci(n_lst[i], t_dct)
	print(t_dct[n_lst[i]])
0