結果

問題 No.657 テトラナッチ数列 Easy
コンテスト
ユーザー twkmath
提出日時 2018-03-11 19:47:33
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,128 bytes
コンパイル時間 82 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 67,732 KB
最終ジャッジ日時 2024-10-15 00:24:41
合計ジャッジ時間 3,713 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 4 TLE * 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])%17
				return t[i]
			elif i-2 in t.keys():
				t[i-1] = (t[i-2]+t[i-3]+t[i-4]+t[i-5])%17
				t[i] = (t[i-1]+t[i-2]+t[i-3]+t[i-4])%17
				return t[i]
			elif i-3 in t.keys():
				t[i-2] = (t[i-3]+t[i-4]+t[i-5]+t[i-6])%17
				t[i-1] = (t[i-2]+t[i-3]+t[i-4]+t[i-5])%17
				t[i] = (t[i-1]+t[i-2]+t[i-3]+t[i-4])%17
				return t[i]
			elif i-4 in t.keys():
				t[i-3] = (t[i-4]+t[i-5]+t[i-6]+t[i-7])%17
				t[i-2] = (t[i-3]+t[i-4]+t[i-5]+t[i-6])%17
				t[i-1] = (t[i-2]+t[i-3]+t[i-4]+t[i-5])%17
				t[i] = (t[i-1]+t[i-2]+t[i-3]+t[i-4])%17
				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