結果

問題 No.657 テトラナッチ数列 Easy
ユーザー twkmath
提出日時 2018-03-11 19:26:04
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
MLE  
実行時間 -
コード長 1,078 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 817,840 KB
最終ジャッジ日時 2024-10-15 00:23:17
合計ジャッジ時間 2,963 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 4 MLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

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