

"""simple docstring"""


import functools
from math import sqrt
from time import time






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				*__SCREAMING_SNAKE_CASE      ,				**__SCREAMING_SNAKE_CASE				)			->			Tuple:
		__lowerCAmelCase: Dict					   =    time()
		__lowerCAmelCase: Tuple					   =    func(*__SCREAMING_SNAKE_CASE      ,				**__SCREAMING_SNAKE_CASE				)
		__lowerCAmelCase: Dict					   =    time()
		if int(end - start				) > 0:
				print(F"{func.__name__} runtime: {(end - start):0.4f} s"				)
		else:
				print(F"{func.__name__} runtime: {(end - start) * 1_0_0_0:0.4f} ms"				)
		return output






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			list[int]:
		if n < 0:
				raise Exception("n is negative"				)
		if n == 0:
				return [0]
		__lowerCAmelCase: Tuple					   =    [0, 1]
		for _ in range(n - 1				):
				fib.append(fib[-1] + fib[-2]				)
		return fib






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			list[int]:

		def fib_recursive_term(__SCREAMING_SNAKE_CASE				) -> int:
				if i < 0:
						raise Exception("n is negative"				)
				if i < 2:
						return i
				return fib_recursive_term(i - 1				) + fib_recursive_term(i - 2				)

		if n < 0:
				raise Exception("n is negative"				)
		return [fib_recursive_term(__SCREAMING_SNAKE_CASE				) for i in range(n + 1				)]






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			list[int]:

		@functools.cache
		def fib_recursive_term(__SCREAMING_SNAKE_CASE				) -> int:
				if i < 0:
						raise Exception("n is negative"				)
				if i < 2:
						return i
				return fib_recursive_term(i - 1				) + fib_recursive_term(i - 2				)

		if n < 0:
				raise Exception("n is negative"				)
		return [fib_recursive_term(__SCREAMING_SNAKE_CASE				) for i in range(n + 1				)]






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			list[int]:
		if n < 0:
				raise Exception("n is negative"				)
		# Cache must be outside recursuive function
		# other it will reset every time it calls itself.
		__lowerCAmelCase: dict[int, int]					   =    {0: 0, 1: 1, 2: 1}  # Prefilled cache

		def rec_fn_memoized(__SCREAMING_SNAKE_CASE				) -> int:
				if num in cache:
						return cache[num]

				__lowerCAmelCase: Optional[Any]					   =    rec_fn_memoized(num - 1				) + rec_fn_memoized(num - 2				)
				__lowerCAmelCase: Optional[Any]					   =    value
				return value

		return [rec_fn_memoized(__SCREAMING_SNAKE_CASE				) for i in range(n + 1				)]






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			list[int]:
		if n < 0:
				raise Exception("n is negative"				)
		if n >= 1_4_7_5:
				raise Exception("n is too large"				)
		__lowerCAmelCase: Union[str, Any]					   =    sqrt(5				)
		__lowerCAmelCase: Optional[Any]					   =    (1 + sqrt_a) / 2
		return [round(phi**i / sqrt_a				) for i in range(n + 1				)]


if __name__ == "__main__":
			__A		     =    30
			time_func(fib_iterative, num)
			time_func(fib_recursive, num)  # Around 3s runtime
			time_func(fib_recursive_cached, num)  # Around 0ms runtime
			time_func(fib_memoization, num)
			time_func(fib_binet, num)





"""simple docstring"""


def 					a__					(					__SCREAMING_SNAKE_CASE = 1_0_0_0				)			->			int:
		__lowerCAmelCase: int					   =    0
		__lowerCAmelCase: Optional[int]					   =    0
		while 1:
				num += 3
				if num >= n:
						break
				total += num
				num += 2
				if num >= n:
						break
				total += num
				num += 1
				if num >= n:
						break
				total += num
				num += 3
				if num >= n:
						break
				total += num
				num += 1
				if num >= n:
						break
				total += num
				num += 2
				if num >= n:
						break
				total += num
				num += 3
				if num >= n:
						break
				total += num
		return total


if __name__ == "__main__":
			print(F'''{solution() = }''')


