AtCoder Beginner Contest 079 - Lucas Number

It is November 18 now in Japan. By the way, 11 and 18 are adjacent Lucas numbers.
You are given an integer N. Find the N-th Lucas number.
Here, the i-th Lucas number L_i is defined as follows:
 - L_0=2
 - L_1=1
 - L_i=L_{i-1}+L_{i-2} (i≥2)

-----Constraints-----
 - 1≤N≤86
 - It is guaranteed that the answer is less than 10^{18}.
 - N is an integer.

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
Print the N-th Lucas number.

-----Sample Input-----
5

-----Sample Output-----
11

 - L_0=2
 - L_1=1
 - L_2=L_0+L_1=3
 - L_3=L_1+L_2=4
 - L_4=L_2+L_3=7
 - L_5=L_3+L_4=11
Thus, the 5-th Lucas number is 11.

Source: atcoder | Difficulty: EASY


Solutions:
N = int(input())
if N == 0:
	print(2)
elif N == 1:
	print(1)
else:
	n_2 = 2
	n_1 = 1
	for _ in range(N - 1):
		n_0 = n_1 + n_2
		n_2 = n_1
		n_1 = n_0
	print(n_0)


n = int(input())
l = [2, 1]
for i in range(n - 1):
	l.append(l[-1] + l[-2])
print(l[n])


n = int(input())
a = 2
b = 1
for i in range(n):
	(a, b) = (b, a + b)
print(a)


import sys
N = int(input())
if N == 1:
	print(1)
	return
ans = 0
L0 = 2
L1 = 1
for i in range(N - 1):
	ans = L0 + L1
	L0 = L1
	L1 = ans
print(ans)


a = int(input())
L = [2, 1]
for i in range(a - 1):
	L.append(L[i] + L[i + 1])
print(L[a])


a0 = 2
a1 = 1
for _ in range(int(input()) - 1):
	(a0, a1) = (a1, a0 + a1)
print(a1)


N = int(input())
L = [2, 1]
for i in range(N - 1):
	if i == 0:
		L.append(L[0] + L[1])
	else:
		L.append(L[i] + L[i + 1])
print(L[-1])


import sys
from io import StringIO
import unittest
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

class TestClass(unittest.TestCase):

	def assertIO(self, input, output):
		(stdout, stdin) = (sys.stdout, sys.stdin)
		(sys.stdout, sys.stdin) = (StringIO(), StringIO(input))
		resolve()
		sys.stdout.seek(0)
		out = sys.stdout.read()[:-1]
		(sys.stdout, sys.stdin) = (stdout, stdin)
		self.assertEqual(out, output)

	def test_入力例_1(self):
		input = '5'
		output = '11'
		self.assertIO(input, output)

	def test_入力例_2(self):
		input = '86'
		output = '939587134549734843'
		self.assertIO(input, output)

def resolve():
	N = int(input())
	print(L(N))

@lru_cache(maxsize=1000)
def L(n):
	if n == 0:
		return 2
	elif n == 1:
		return 1
	else:
		return L(n - 1) + L(n - 2)

def __starting_point():
	resolve()
__starting_point()


n = int(input())
a = 2
b = 1
for _ in range(n):
	(a, b) = (b, a + b)
print(a)


N = int(input())
(a, b) = (2, 1)
for _ in range(N):
	(a, b) = (b, a + b)
print(a)


a = int(input())
b = [2, 1]
for i in range(a - 1):
	b.append(b[i] + b[i + 1])
print(b[-1])


n = int(input())
a = [2, 1]
for i in range(2, n + 1):
	a.append(a[i - 1] + a[i - 2])
print(a[n])


N = int(input())
L = [2, 1]
for i in range(N - 1):
	L.append(L[-1] + L[-2])
print(L[N])


n = int(input())
l = [2, 1]
for _ in range(100):
	l.append(l[-1] + l[-2])
print(l[n])


n = int(input())
L = [2, 1]
for i in range(86):
	L.append(L[i] + L[i + 1])
print(L[n])


n = int(input())
list_lucas = [2, 1]
lucas = 0
for i in range(0, n - 1):
	lucas = list_lucas[i] + list_lucas[i + 1]
	list_lucas.append(lucas)
	lucas = 0
print(list_lucas[-1])


N = int(input())
L = [2, 1]
for _ in range(88):
	L.append(L[-1] + L[-2])
print(L[N])


n = int(input())
a = [2, 1]
for x in range(n - 1):
	a.append(a[x] + a[x + 1])
print(a[-1])


n = int(input())
l = [2, 1]
for _ in range(n - 1):
	l += [l[-1] + l[-2]]
print(l[n])


n = int(input())
(l0, l1) = (2, 1)
for i in range(2, n + 1):
	l = l0 + l1
	(l0, l1) = (l1, l)
print(l1)


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
if n == 1:
	print(1)
	return
a = 2
b = 1
now = 3
count = 2
for i in range(2, n):
	a = b
	b = now
	now = a + b
print(now)


N = int(input())
L = [2, 1]
while len(L) <= N:
	L.append(L[-2] + L[-1])
print(L[-1])


n = int(input())
L0 = 2
L1 = 1
for i in range(n):
	(L0, L1) = (L1, L0 + L1)
print(L0)


N = int(input())
lucas_list = []
for i in range(N + 1):
	if i == 0:
		lucas_list.append(2)
	elif i == 1:
		lucas_list.append(1)
	else:
		lucas_list.append(lucas_list[-1] + lucas_list[-2])
else:
	print(lucas_list[-1])


L = [2, 1]
for i in range(85):
	L.append(L[-1] + L[-2])
print(L[int(input())])


l = [2, 1]
for _ in range(85):
	l += [l[-2] + l[-1]]
print(l[int(input())])


n = int(input())
if n == 1:
	print(1)
	return
x = 2
y = 1
ans = 0
for i in range(n - 1):
	ans = x + y
	x = y
	y = ans
print(ans)


(a, b) = (2, 1)
exec('a,b=b,a+b;' * int(input()))
print(a)


L = [2, 1]
for i in range(2, 100):
	L.append(L[i - 1] + L[i - 2])
print(L[int(input())])


N = int(input())
ls = [0] * (N + 1)
(ls[0], ls[1]) = (2, 1)
for i in range(2, N + 1):
	ls[i] += ls[i - 1] + ls[i - 2]
print(ls[N])


n = int(input())
luca = [2, 1]
if n >= 2:
	for i in range(n - 1):
		luca.append(luca[-1] + luca[-2])
	print(luca[-1])
else:
	print(1)


N = int(input())
r = [2, 1]
for _ in range(N - 1):
	r.append(r[-1] + r[-2])
print(r[-1])


L = [2, 1]
for _ in [0] * 85:
	L += [L[-2] + L[-1]]
print(L[int(input())])


N = int(input())
res = [2, 1]
for i in range(N - 1):
	res.append(res[-1] + res[-2])
print(res[-1])


l = [2, 1]
n = int(input())
i = 0
while i != n:
	l.append(l[i] + l[i + 1])
	i += 1
print(l[n])


N = int(input())
s = 2
t = 1
for i in range(0, N):
	u = s + t
	(s, t, u) = (t, u, s)
print(s)


N = int(input())
prev = 2
now = 1
for i in range(N - 1):
	(prev, now) = (now, now + prev)
print(now)


n = int(input())
data = [0] * 87
data[0] = 2
data[1] = 1
if n >= 2:
	for i in range(2, n + 1):
		data[i] = data[i - 1] + data[i - 2]
print(data[n])


N = int(input())
(a, b) = (2, 1)
for i in range(N - 1):
	(a, b) = (b, a + b)
print(b)


N = int(input())
(L1, L2) = (2, 1)
L3 = 1
x = 1
for i in range(N - 1):
	if x == 1:
		L1 = L1 + L2
		L3 = L1
		x = 2
	else:
		L2 = L1 + L2
		L3 = L2
		x = 1
print(L3)


N = int(input())
L = [2, 1]
if N == 1:
	print(1)
	return
for i in range(2, N + 1):
	L[i % 2] = sum(L)
print(L[N % 2])


x = [2, 1]
for _ in range(100):
	x.append(x[-2] + x[-1])
print(x[int(input())])


N = int(input())
l1 = 2
l2 = 1
for i in range(N - 1):
	(l1, l2) = (l2, l1 + l2)
print(l2)


n = int(input())
(a, b) = (2, 1)
for i in range(2, n + 1):
	c = a + b
	(a, b) = (b, c)
print(c if n != 1 else 1)


n = int(input())
r = [2, 1]
for i in range(2, 87):
	r.append(r[i - 2] + r[i - 1])
print(r[n])


N = int(input())
data = [2]
data.append(1)
for i in range(2, N + 1):
	data.append(data[i - 1] + data[i - 2])
print(data[N])


N = int(input())
L = [2, 1]
i = 0
while i < N:
	buff = L[0]
	L[0] = L[1]
	L[1] += buff
	i += 1
print(L[0])


n = int(input())
l = [2, 1]
for i in range(n - 1):
	l[i % 2] = l[0] + l[1]
print(l[n % 2])


N = int(input())
dp = [[] for i in range(87)]
dp[0] = 2
dp[1] = 1
for i in range(2, 87):
	dp[i] = dp[i - 1] + dp[i - 2]
	if i == N:
		print(dp[i])
		break
else:
	print(dp[N])


N = int(input())
l = [2, 1]
for _ in range(N - 1):
	l.extend([l[-1] + l[-2]])
print(l[-1])


n = int(input())
(a, b) = (2, 1)
c = 1
while c < n:
	(a, b) = (b, a + b)
	c += 1
print(b)


n = int(input())
L = [2, 1]
for i in range(2, n + 1):
	L += [L[-1] + L[-2]]
print(L[-1])


(a, b) = (2, 1)
for _ in [0] * int(input()):
	(a, b) = (b, a + b)
print(a)


N = int(input())
(L0, L1) = (2, 1)
for _ in range(N - 1):
	(L0, L1) = (L1, L0 + L1)
print(L1)


N = int(input())
L = [2, 1] + [0] * (N - 1)
for i in range(2, N + 1):
	L[i] = L[i - 1] + L[i - 2]
print(L[N])


(l, m) = (2, 1)
for _ in range(2, int(input()) + 1):
	(l, m) = (m, l + m)
print(m)


n = int(input())
(l1, l2) = (2, 1)
for i in range(n):
	(l1, l2) = (l2, l1 + l2)
print(l1)


N = int(input())
A = 2
B = 1
for i in range(N):
	(A, B) = (B, A + B)
print(A)


def answer(n: int) -> int:
	if n == 1:
		return 1
	two_previous_l = 2
	previous_l = 1
	l = 3
	for _ in range(n - 2):
		two_previous_l = previous_l
		previous_l = l
		l = previous_l + two_previous_l
	return l

def main():
	n = int(input())
	print(answer(n))

def __starting_point():
	main()
__starting_point()


N = int(input())
l = [2, 1]
for i in range(90):
	l.append(l[-2] + l[-1])
print(l[N])


(a, b) = (2, 1)
for i in [0] * int(input()):
	(a, b) = (b, a + b)
print(a)


n = int(input())
(a, b) = (1, 2)
i = 2
while i <= n:
	(a, b) = (a + b, a)
	i += 1
print(a)


n = int(input())
num_list = [0] * (n + 1)
num_list[0] = 2
num_list[1] = 1
for i in range(2, n + 1, 1):
	num_list[i] = num_list[i - 1] + num_list[i - 2]
ans = num_list[n]
print(ans)


N = int(input())
v = [2, 1]
for i in range(N):
	v.append(v[i] + v[i + 1])
print(v[N])


N = int(input())

def luca(n):
	a = 1
	b = 2
	for i in range(n):
		(a, b) = (a + b, a)
	return b
print(luca(N))


import numpy as np
n = int(input())
l = np.zeros(87, dtype=int)
l[0] = 2
l[1] = 1
for i in range(2, 87):
	l[i] = l[i - 1] + l[i - 2]
print(l[n])


A = [2, 1]
for i in range(86):
	A.append(A[0 + i] + A[1 + i])
print(A[int(input())])


n = int(input())
p = [2, 1]
for i in range(n - 1):
	p.append(p[i] + p[i + 1])
print(p[-1])


N = int(input())
l = [2, 1]
if N == 1:
	print(1)
else:
	for i in range(2, N + 1):
		l.append(l[i - 2] + l[i - 1])
	print(l[-1])


l = [2, 1]
for i in range(100):
	l.append(l[-1] + l[-2])
print(l[int(input())])


n = int(input())
l = [0] * (n + 1)
l[0] = 2
l[1] = 1
if n == 1:
	ans = l[1]
else:
	for i in range(2, n + 1):
		l[i] = l[i - 1] + l[i - 2]
	ans = l[-1]
print(ans)


N = int(input())
if N == 0:
	print(2)
	return
elif N == 1:
	print(1)
	return
L_2 = 2
L_1 = 1
for i in range(N - 1):
	L = L_1 + L_2
	L_2 = L_1
	L_1 = L
print(L)


n = int(input())
(L0, L1) = (2, 1)
if n == 1:
	print(L1)
else:
	for _ in range(n - 1):
		L = L0 + L1
		(L0, L1) = (L1, L)
	print(L)


n = int(input())
l = [2, 1]
while len(l) < n + 1:
	l.append(l[-1] + l[-2])
print(l[-1])


n = int(input())
luk = [2, 1]
for i in range(2, n + 1):
	luk.append(luk[i - 1] + luk[i - 2])
print(luk[-1])


q = [2, 1]
for i in range(2, 87):
	q.append(q[i - 1] + q[i - 2])
print(q[int(input())])


(k, l) = (-1, 2)
for i in range(int(input())):
	(k, l) = (l, k + l)
print(l)


N = int(input())
ANS = [2, 1]
for i in range(1, N):
	ANS.append(ANS[i] + ANS[i - 1])
print(ANS[N])


n = int(input())
luca = [0 for i in range(n + 1)]
luca[0] = 2
luca[1] = 1
for j in range(2, n + 1):
	luca[j] = luca[j - 1] + luca[j - 2]
print(luca[n])


import sys
input = sys.stdin.readline

def main():
	numbers = [2, 1]
	number = int(input())
	for i in range(2, number + 1):
		numbers.append(numbers[i - 1] + numbers[i - 2])
	print(numbers[-1])

def __starting_point():
	main()
__starting_point()


t = [2, 1]
for i in range(2, 90):
	t.append(t[i - 1] + t[i - 2])
print(t[int(input())])


L = [2, 1]
for _ in range(int(input()) - 1):
	L.append(L[-2] + L[-1])
print(L[-1])


from functools import lru_cache
N = int(input())

@lru_cache(86)
def lucas(x):
	if x == 0:
		return 2
	if x == 1:
		return 1
	else:
		return lucas(x - 1) + lucas(x - 2)
print(lucas(N))


n = int(input())
Luca = [0] * 100
Luca[0] = 2
Luca[1] = 1
for i in range(2, n + 1):
	Luca[i] = Luca[i - 1] + Luca[i - 2]
print(Luca[n])


(k, l) = (-1, 2)
for i in [0] * int(input()):
	(k, l) = (l, k + l)
print(l)


i = int(input())
a = 2
b = 1
c = 0
while i > 1:
	c = b
	b = b + a
	a = c
	i -= 1
print(b)


from collections import defaultdict

def mapt(fn, *args):
	return tuple(map(fn, *args))

def Input():
	return mapt(int, input().split(' '))

def main():
	n = int(input())
	l = defaultdict(int)
	(l[0], l[1]) = (2, 1)
	for i in range(2, n + 1):
		l[i] = l[i - 1] + l[i - 2]
	print(l[n])
main()


n = int(input())
a_ = 2
a = 1
for i in range(n - 1):
	(a, a_) = (a + a_, a)
print(a)


n = int(input())
a = [0] * (n + 1)
a[0] = 2
a[1] = 1
for i in range(2, n + 1):
	a[i] = a[i - 1] + a[i - 2]
print(a[n])


n = int(input())
a = 2
b = 1
i = 0
while i < n:
	d = a
	a = b
	b = d + b
	i = i + 1
print(a)


n = int(input())
s = []
s.append(2)
s.append(1)
if n == 1:
	print('1')
	return
else:
	for i in range(2, 87):
		k = s[i - 2] + s[i - 1]
		s.append(k)
		if i == n:
			print(s[i])
			return


n = int(input())
f = [2, 1]
for i in range(2, n + 1):
	f.append(f[i - 1] + f[i - 2])
print(f[-1])


import sys
import copy
import math
import itertools
import numpy as np
N = int(input())
L = [2, 1]
for i in range(N - 1):
	L.append(L[i] + L[i + 1])
print(L[N])


from functools import lru_cache

@lru_cache
def lucas(n):
	if n == 0:
		return 2
	if n == 1:
		return 1
	else:
		return lucas(n - 1) + lucas(n - 2)
N = int(input())
print(lucas(N))


a = [2, 1]
for i in range(90):
	a.append(a[-1] + a[-2])
print(a[int(input())])


lis = [2, 1]
for i in range(0, 100):
	lis.append(lis[i] + lis[i + 1])
print(lis[int(input())])


a0 = 2
a = 1
for _ in range(1, int(input())):
	a += a0
	a0 = a - a0
print(a)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20

def I():
	return int(input())

def F():
	return float(input())

def S():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LS():
	return input().split()

def resolve():
	N = I()
	lucas = [0] * (N + 1)
	lucas[0] = 2
	lucas[1] = 1
	for i in range(N - 1):
		lucas[i + 2] = lucas[i] + lucas[i + 1]
	print(lucas[-1])

def __starting_point():
	resolve()
__starting_point()


l = [2, 1] + [0] * 100
for i in range(2, 87):
	l[i] = l[i - 1] + l[i - 2]
print(l[int(input())])


n = int(input())
dp = [2, 1]
for i in range(n - 1):
	dp.append(dp[-1] + dp[-2])
print(dp[-1])


x = int(input())
l = [2, 1]
for i in range(2, 87):
	l.append(l[-1] + l[-2])
print(l[x])


def __starting_point():
	n = int(input())
	A = [2, 1]
	for i in range(2, n + 1):
		A.append(A[i - 2] + A[i - 1])
	print(A[n])
__starting_point()


n = int(input())
a = [2, 1]
for i in range(n):
	a += [sum(a[-2:])]
print(a[n])


n = int(input())
li = [2, 1]
for i in range(1, n):
	li.append(li[i] + li[i - 1])
print(li[-1])


L = [2, 1]
while len(L) < 90:
	L.append(L[-2] + L[-1])
print(L[int(input())])


N = int(input())
L = [2, 1]
for n in range(2, N + 1):
	L.append(L[n - 1] + L[n - 2])
print(L[-1])


a = int(input())
L = 2
L1 = 1
L2 = 0
for i in range(a):
	L2 = L + L1
	L = L1
	L1 = L2
print(L)


n = int(input())
L = [2, 1]
for _ in range(n - 1):
	L.append(sum(L[-2:]))
print(L[-1])


l = [1, 3]
for i in range(84):
	l.append(l[i] + l[i + 1])
print(l[int(input()) - 1])


N = int(input())
(x, y) = (1, 2)
for _ in range(N - 1):
	(x, y) = (x + y, x)
print(x)


n = int(input())
if n == 0:
	print(2)
	return
elif n == 1:
	print(1)
	return
q = [2, 1]
for i in range(2, 88):
	m = q[i - 1] + q[i - 2]
	q.append(m)
print(q[n])


n = int(input())
arr = [0 for i in range(n + 1)]
arr[0] = 2
arr[1] = 1
for i in range(2, n + 1):
	arr[i] = arr[i - 1] + arr[i - 2]
print(arr[n])


n = int(input())
if n == 1:
	print(1)
elif n == 2:
	print(3)
else:
	ans = 0
	num_1 = 2
	num_2 = 1
	for i in range(n - 1):
		ans = num_1 + num_2
		(num_1, num_2) = (num_2, ans)
	print(ans)


n = int(input())
l0 = 2
l1 = 1
if n == 1:
	print(l1)
else:
	for i in range(n - 1):
		ln = l0 + l1
		l0 = l1
		l1 = ln
	print(ln)


n = int(input())
l = [2, 1]
while len(l) <= n:
	l += [sum(l[-2:])]
print(l[n])


(l, m) = (2, 1)
for i in range(int(input()) - 1):
	(l, m) = (m, l + m)
print(m)


li = [2, 1]
N = int(input())
for i in range(N):
	li.append(li[i] + li[i + 1])
print(li[N])


def resolve():
	N = int(input())
	memo = [0 for _ in range(N + 1)]
	memo[:2] = [2, 1]
	for i in range(2, N + 1):
		memo[i] = memo[i - 1] + memo[i - 2]
	print(memo[N])

def __starting_point():
	resolve()
__starting_point()


(l0, l1) = (2, 1)
for i in range(int(input())):
	(l0, l1) = (l1, l0 + l1)
print(l0)


n = int(input())
import sys
dp = [0] * (n + 3)
dp[0] = 2
dp[1] = 1
if n <= 1:
	print(dp[n])
	return
for i in range(2, n + 1):
	dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])


n = int(input())

def fibonacci(n):
	fib = [2, 1]
	for i in range(2, n):
		fib.append(fib[i - 2] + fib[i - 1])
	return fib[n - 1]
print(fibonacci(n + 1))


N = int(input())
l_list = [2, 1]
for i in range(2, N + 1):
	a = l_list[i - 1] + l_list[i - 2]
	l_list.append(a)
print(l_list[N])


lst = list()
lst.append(2)
lst.append(1)
n = int(input())
for i in range(2, n + 1):
	ans = lst[i - 2] + lst[i - 1]
	lst.append(ans)
print(lst[n])


n = int(input())
l = [2, 1]
if n == 0:
	print(2)
elif n == 1:
	print(1)
else:
	for i in range(n - 1):
		l.append(l[-1] + l[-2])
	print(l[-1])


N = int(input())
l = 2
r = 1
for i in range(N - 1):
	tmp = r
	r += l
	l = tmp
print(r)


N = int(input())
if N == 1:
	print(1)
	return
L1 = 1
L0 = 2
for i in range(2, N + 1):
	LC = L1 + L0
	L0 = L1
	L1 = LC
print(LC)


N = int(input())
a = 2
b = 1
for x in range(N - 1):
	c = b
	b = a + b
	a = c
print(b)