Problem:


Score : 200 points

Problem Statement

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 1

5

Sample Output 1

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.

Sample Input 2

86

Sample Output 2

939587134549734843



Sample input:
5


Sample output:
11

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(raw_input())

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

Submission status: Accepted

Solution code:
# coding: utf-8

def Lucas(n):
    a, b, c = 2, 1, 3
    while n != 0:
        a, b, c = b, c, b+c
        n -=1
    
    print a

Lucas(int(raw_input()))

Submission status: Accepted

Solution code:
# -*- coding:utf-8

num = int(input())

L = []
L.append(2)
L.append(1)

for i in range(num):
		L.append(L[i]+L[i+1])

print(L[num])

Submission status: Accepted

Solution code:
N=int(input())
L=[0 for i in range(N+1)]

L[0]=2
L[1]=1

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

Submission status: Accepted

Solution code:
n = int(input())
i = 1
prev = 2
x = [2, 1]

while i < n:
    if i == n:
        break
    x.append(x[i-1] + x[i])
    i = i + 1

print(x[n])

Submission status: Accepted

Solution code:
N=int(input())
A=[0 for i in range(N)]
A[0]=1
for i in range(N-1):
    if(i==0):
        A[i+1]=A[i]+2
    else:
        A[i+1]=A[i]+A[i-1]
print(A[N-1])

Submission status: Accepted

Solution code:
def calc(n, a, b):
    if n == 1:
        return b
    ls = [0 for i in range(n + 1)]
    ls[0], ls[1] = a, b
    for i in range(2, n + 1):
        ls[i] = ls[i - 1] + ls[i - 2]
    return ls[-1]

n = int(input())
print(calc(n, 2, 1))

Submission status: Accepted

Solution code:
def calc(n, a, b):
    if n == 1:
        return b
    ls = [0 for i in range(n + 1)]
    ls[0] = 2
    ls[1] = 1
    for i in range(2, n + 1):
        ls[i] = ls[i - 1] + ls[i - 2]
    return ls[-1]

n = int(input())
print(calc(n, 2, 1))

Submission status: Accepted

Solution code:
n = int(input())

lucas = [2, 1]
for i in range(2, n+1):
    lucas.append(lucas[i-1] + lucas[i-2])

print(lucas[n])

Submission status: Accepted

Solution code:
def main():
    N = int(input())

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

    print(L[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#-*- coding:utf-8 -*-
N = int(input())

def lucas(M):
    a = 2
    b = 1
    
    if M > 1:
        for x in range(N-1):
            a,b = b,a+b
        return b
    elif M == 1:
        return 1
    elif M == 0:
        return 2 

print(lucas(N))

Submission status: Accepted

Solution code:
# coding: utf-8

# リュカ数定義
L = [2, 1]
# 整数の入力
n = int(input())
# リュカ数計算
for i in range(1, n):
    L.append(L[i - 1] + L[i])
# 出力
print(L[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:utf-8
import numpy as np

N = int(input())

ryuka = [2,1,3]

for i in range(N+1):
	if i>=3:
		R = (ryuka[i-1])+(ryuka[i-2])
		ryuka.append(R)
	else:
		pass

print(ryuka[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python

N=int(input())
A=2
B=1
sum=1

for i in range(0, N-1):
    # print(sum)
    sum=A+B
    A=B
    B=sum

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc079/tasks/abc079_b

"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


@lru_cache()
def solve(N):
    if N == 0:
        return 2
    elif N == 1:
        return 1
    return solve(N - 1) + solve(N - 2)



def main(args):
    N = int(input())
    ans = solve(N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
a = int(input())
L0 =2
L1 =1
if a==0:
    print(L0)
elif a==1:
    print(L1)
else:
    for i in range(2, a+1):
        temp = L1
        L1 = L1 +L0
        L0 = temp

    print(L1)

Submission status: Accepted

Solution code:
n = int(input())

l = []
l.append(2)
l.append(1)

if n>1:
	for i in range(2, n+1):
		l.append(l[i-1] + l[i-2])

print(l[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# N < 90なのでテーブルにする必要ある？
table = [0]*90
def L(i):
    if i == 0:
        table[i] = 2
    elif i == 1:
        table[i] = 1
    else:
        table[i] = table[i- 1] + table[i-2]

s = int(input())
for i in range(s + 1):
    L(i)
print(table[s])
# tleした

Submission status: Accepted

Solution code:
#!/usr/bin/env python

N = int(input())
Lin2 = 2
Lin1 = 1

if N > 1:
    for i in range(N-1):
        Li = Lin1 + Lin2
        Lin2 = Lin1
        Lin1 = Li
else:
    Li = 1

        
print(Li)

Submission status: Accepted

Solution code:
N = int(input())
# N = 86


def f(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    elif n == 2:
        return 3
    return 2 * f(n - 2) + f(n - 3)


def g(n):
    L = [0] * (n + 1)
    L[0] = 2
    L[1] = 1
    for i in range(2, n + 1):
        L[i] = L[i - 1] + L[i - 2]

    return L[-1]


print(g(N))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    m = {0: 2, 1: 1}
    def f(i):
        if i in m:
            return m[i]
        a = f(i-1)
        b = f(i-2)
        m[i] = a+b
        return m[i]


    return f(n)



print(main())

Submission status: Accepted

Solution code:
#coding:utf-8
import fileinput

for row in fileinput.input():
    N = int(row.strip())
    L = 2
    R = 1
    for i in range(N-1):
        L_N = L + R
        L = R
        R = L_N
    if N>1:
        print L_N
    elif N==1:
        print R
    elif N==0:
        print L

Submission status: Accepted

Solution code:
x = input()
N = int(x)

a = 2
luca = 1

for i in range(1,N):
  c = luca
  luca = a+luca
  a = c
  
print(luca)

Submission status: Accepted

Solution code:
luca = list()
luca.append(2)
luca.append(1)
for i in xrange(2, input()+1):
    luca.append(luca[i-1]+luca[i-2])
print luca[-1]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
res = [0 for i in range(100)]
res[0] = 2
res[1] = 1
for i in range(2, N+1):
	res[i] = res[i - 1] + res[i - 2]
print(res[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input())
L = [2, 1]
for _ in range(N - 1):
    L.append(L[-1] + L[-2])
print(L[N])

Submission status: Accepted

Solution code:
n = int(raw_input())

ryuka = [2,1]

for i in range(n-1):
    ryuka.append(ryuka[i]+ryuka[i+1])

print ryuka[n]

Submission status: Accepted

Solution code:
def fib(n):
    memo = [0] * n
    memo[0:2] = [2, 1]
    for i in range(2, n):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n - 1]


def solve():
    N = int(input())
    print(fib(N + 1))
    

solve()

Submission status: Accepted

Solution code:
N = int(input())
l0 = 2
l1 = 1
for i in range(N):
    temp = l0 + l1
    l0 = l1
    l1 = temp
print (l0)

Submission status: Accepted

Solution code:
def main():
	n = int(input())
	dp = [2,1]
	for i in range(2,100):
		dp.append(dp[i-2]+dp[i-1])
	print(dp[n])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

def calc(p, s):
    return p + s

def main():
    l0 = 2
    l1 = 1
    if N == 1:
        print(l1)
    else:
        p = l0
        s = l1
        for i in range(N - 1):
            temp = calc(p, s)
            p = s
            s = temp
        print(s)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
Lucas=[2,1]
while Lucas[-1] < 1000000000000000000:
    Lucas.append(Lucas[-1]+Lucas[-2])
print(Lucas[int(input())])

Submission status: Accepted

Solution code:
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if table[n-1] != 0:
        t1 = table[n-1]
    else:
        table[n-1] = lucas(n-1)
        t1 = table[n-1]
    if table[n-2] != 0:
        t2 = table[n-2]
    else:
        table[n-2] = lucas(n-2)
        t2 = table[n-2]
    return t1 + t2


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

if __name__ == '__main__':
    table = [0 for _ in range(86)]
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [ 2, 1 ]
for tmp in range(85):
    a.append(a[tmp]+a[tmp+1])
print(a[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
l = [0 for _ in range(100)]
l[0] = 2
l[1] = 1
for i in range(2,100):
    l[i] = l[i-1]+l[i-2]

n = int(raw_input())
print l[n]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = int(input())
n = {0:2, 1:1}
if s > 1:
  for i in range(2, s+1):
  	n[i] = n[i-1] + n[i-2]
print(n[s])

Submission status: Accepted

Solution code:

def lucas(x):
  list = []
  list.append(2)
  list.append(1)
  i = 2
  while i <= x:
    list.append(list[i-1]+list[i-2])
    i += 1
  return list
      
 
if __name__ == '__main__':
  inputstr = input()
  num = int(inputstr)
  list = lucas(num)
  ans = list[num]
  print(ans,flush=True)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input())
L = [0] * (N + 1)
L[0] = 2
if N == 1:
    print(1)
else:
    L[1] = 1
    for i in range(2, N + 1):
        L[i] = L[i - 1] + L[i - 2]
    print(L[N])

Submission status: Accepted

Solution code:
def Luca(N):
    L = [2,1]

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

print(Luca(N))

Submission status: Accepted

Solution code:
n = input()

l = [0 for i in range(87)]

l[0] = 2
l[1] = 1

for i in range(2, n + 1):
    l[i] = l[i-1] + l[i-2]

print l[n]

Submission status: Accepted

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

    print(c)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())
memo = [0] * 87
def luca(n):

  if n == 0:
    return 2
  elif n == 1:
    return 1

  if not memo[n]:
    memo[n] = luca(n - 2) + luca(n - 1)
  return memo[n]

print(luca(N))

Submission status: Accepted

Solution code:
lucas_list = [-1 for i in range(87)]
lucas_list[0] = 2
lucas_list[1] = 1

def lucas(n):
    if lucas_list[n] >= 0:
        return lucas_list[n]
    lucas_list[n] = lucas(n-1)+lucas(n-2)
    return lucas_list[n]

def solve():
    N = int(input())
    print(lucas(N))

solve()

Submission status: Accepted

Solution code:
n = input()
l = [0]*87
l[0] = 2
l[1] = 1
for x in range(2,87):
    l[x] = l[x-1] + l[x-2]
print(l[n])

Submission status: Accepted

Solution code:
#ABC079B

n=int(raw_input())
l=[0 for i in xrange(87)]
l[0]=2
l[1]=1
for i in xrange(2,n+1):
 l[i]=l[i-1]+l[i-2]
print l[n]

Submission status: Accepted

Solution code:
# 入力
N = int(input())
# 初期値(l_0, l_1)
L = [2, 1]
# 計算
if N == 1:
    print("1")
else:
    for i in range(N-1):
        L.append(L[i+1] + L[i])
    print(L[-1])

Submission status: Accepted

Solution code:
P = 10**18
A = []
A.append(2)
A.append(1)
n = int(input())
for i in range(2,100000):
    A.append((A[i-1] + A[i-2])%P)
print(A[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

N = int(raw_input())
L = [2, 1]

for i in range(90):
    L += [L[-2] + L[-1]]

print L[N]

Submission status: Accepted

Solution code:
N = int(input())

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

print(L[-1])

Submission status: Accepted

Solution code:
memo = [2, 1] + 85 * [0]
def luca(n):
	if memo[n] != 0 :
		return memo[n]
	else :
		memo[n] = luca(n - 1) + luca(n - 2)
		return memo[n]

n = int(input())
print(luca(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

N = int(input())

L0=2
L1=1

temp=L1
for i in range(N-1):
	temp=L0+L1
	L0=L1
	L1=temp
print(temp)

Submission status: Accepted

Solution code:
N = int(input())

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

print(L[N])

Submission status: Accepted

Solution code:
l = [2, 1]
for x in xrange(100):
    l.append(l[-2] + l[-1])
print l[input()]

Submission status: Accepted

Solution code:

L0 = 2
L1 = 1
L = L1 + L0

N = int(input())

for i in range(N - 2):
  
  L0 = L1
  L1 = L
  L = L1 + L0

if N == 1:
  print(L1)
elif N == 2:
  print(L1 + L0)
else:
  print(L)

Submission status: Accepted

Solution code:
N = int(input())
array = [2,1]
if N >= 2:
    for i in range(N-1):
        array.append(int(array[i])+int(array[i+1]))
    print(int(array[N]))
    #print(array)
else:
    print(int(array[N]))

Submission status: Accepted

Solution code:
#!/user/bin/python
# coding: UTF-8

N = int(raw_input())

L = [2, 1, 3, 4,
7,
11,
18,
29,
47,
76,
123,
199,
322,
521,
843,
1364,
2207,
3571,
5778,
9349,
15127,
24476,
39603,
64079,
103682,
167761,
271443,
439204,
710647,
1149851,
1860498,
3010349,
4870847,
7881196,
12752043,
20633239,
33385282,
54018521,
87403803,
141422324,
228826127,
370248451,
599074578,
969323029,
1568397607,
2537720636,
4106118243,
6643838879,
10749957122,
17393796001,
28143753123,
45537549124,
73681302247,
119218851371,
192900153618,
312119004989,
505019158607,
817138163596,
1322157322203,
2139295485799,
3461452808002,
5600748293801,
9062201101803,
14662949395604,
23725150497407,
38388099893011,
62113250390418,
100501350283429,
162614600673847,
263115950957276,
425730551631123,
688846502588399,
1114577054219522,
1803423556807921,
2918000611027443,
4721424167835364,
7639424778862807,
12360848946698171,
20000273725560978,
32361122672259149,
52361396397820127,
84722519070079276,
137083915467899403,
221806434537978679,
358890350005878082,
580696784543856761,
939587134549734843]

print L[N]

Submission status: Accepted

Solution code:
a=input()
x=2
y=1
z=1
for i in range(a-1):
    z=x+y
    x=y
    y=z

z=str(z)
print z

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

F = []
F.append(2)
F.append(1)

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

Submission status: Accepted

Solution code:
n = int(input())
lucas = []
lucas.append(2)
lucas.append(1)
for index in range(2,n+1):
    lucas.append(lucas[index-2] + lucas[index-1])
print(lucas[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = str, input()
num = int(N[1])

L0 = 2
L1 = 1
x = 1
for i in range(1, num):
    x = L1 + L0
    L0 = L1
    L1 = x

print(x)

Submission status: Accepted

Solution code:
n = int(input())

l0 = 2
l1 = 1
if n == 1:
    print(l1)
else:
    ans = 0
    for i in range(n-1):
        ans = l0 + l1
        l0 = l1
        l1 = ans
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n = 90
    a = [0 for i in range(n)]
    a[0],a[1] = 2,1

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

    print(a[int(input())])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/opt/local/bin/python3

from sys import stdin

def solve(N):
  l = [2, 1]
  if N <= 0: return l[N]
  for i in range(2, N + 1):
    lx = l[0] + l[1]
    l[0] = l[1]
    l[1] = lx
  return l[1]

N = int(stdin.readline())
print(solve(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

ans = 0
a = 2
b = 1
if N == 0:
  ans = a
elif N == 1:
  ans = b
else:
  for i in range(N - 1):
    ans = a + b
    a = b
    b = ans

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(raw_input())

def lucas(n):
	if n == 0:
		return 2
	elif n == 1:
		return 1

	pre_num = 2
	cur_num = 1
	for i in range(1, n):
		rtn_num = cur_num + pre_num
		pre_num = cur_num
		cur_num = rtn_num
	return rtn_num

print(lucas(n))

Submission status: Accepted

Solution code:
import sys

DBG_FLAG = 0

def p_dbg(str):
    if(DBG_FLAG == 1):
        sys.stdout.flush()
        print str

# TIME OVER
# def lucas_num(num):
#     if num == 0:
#         luca = 2
#     elif num == 1:
#         luca = 1
#     else:
#         luca = lucas_num(num-1)+lucas_num(num-2)

#     return luca

def lucas_num(num):
    array = []
    array.append(2) # i=0
    array.append(1) # i=1
    p_dbg('array' + str(array))
    count = 2
    while count <= num:
        l1 = array[count -1]
        l2 = array[count -2]
        array.append(l1 + l2)
        count = count + 1

    p_dbg('array' + str(array))
    return array[num]

# get num
num = int(raw_input())
p_dbg('num : ' + str(num))

print lucas_num(num)

Submission status: Accepted

Solution code:
# coding: utf-8
N=int(input())
lst=[2,1]
for i in range(N):
    lst.append(lst[i]+lst[i+1])
print(lst[N])

Submission status: Accepted

Solution code:
# coding: utf-8

N = int(raw_input())

a, b, c = 2, 1, 3

if N == 0:
    print a
elif N == 1:
    print b
elif N == 2:
    print c

else:
    for i in range(N-2):
        a, b, c = b, c, (b+c)
    print c

Submission status: Accepted

Solution code:
a = int(input())
R0 = 3
R1 = 2
R2 = 1
R = int((a-1)/3)
if a == 1:
  print("1")
elif a == 2:
  print("3")
elif a == 3:
  print("4")
else:
  for i in range(R):
    R1 = R2+R0
    R2 = R0+R1
    R0 = R1+R2
  if a%3 == 0:
    R1 = R2+R0
    print(R1)
  elif a%3 == 1:
    print(R2)
  else:
    print(R0)

Submission status: Accepted

Solution code:
N = int(input())
ryuka = [0] * (N+1)

ryuka[0] = 2
ryuka[1] = 1

for i in range(2,N+1):
	ryuka[i] = ryuka[i-1] + ryuka[i-2]

print(ryuka[N])

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import lru_cache

@lru_cache()
def function(n):
    if n == 0: return 2
    if n == 1: return 1
    return function(n-1)+function(n-2)

num = int(input())

print(function(num))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)

if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    lucas0 = 2
    lucas1 = 1
    lucas = lucas0 + lucas1
    prev_lucas = lucas1
    for i in range(2, n):
        next_lucas = lucas + prev_lucas
        prev_lucas = lucas
        lucas = next_lucas
    print(lucas)

Submission status: Accepted

Solution code:
import sys,collections
sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()

lu = [0]*87
lu[0] = 2
lu[1] = 1

def luka(n):
    return lu[n-1] + lu[n-2]

for i in range(2,87):
    lu[i] = luka(i)

print(lu[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def ryuka(i):
    if i == 0:
        return 2
    elif i == 1:
        return 1
    else:
        return ryuka(i-1) + ryuka(i-2)

def eryuka(i):
    a = 2
    b = 1
    for _ in range(i):
        a, b = b, a+b
    return a


n = int(input())
print (eryuka(n))

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import lru_cache


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


if __name__ == "__main__":
    n = int(input())
    dict = {0:2, 1:1}
    print(test2(n))

Submission status: Accepted

Solution code:
def luca(a, b, num, c=0):
    if c == num:
        print(a)
    else:
        c += 1
        luca(b, a+b, num, c)

n = int(input())
luca(2, 1, n)

Submission status: Accepted

Solution code:

n = int(input())

ans = 4
pre = 1
prepre = 2

if n == 1:
    ans = 1
elif n == 2:
    ans = 3
elif n == 3:
    ans = 4
else:
    for n in range(n - 3):
        ans += pre + prepre
        a = prepre
        prepre = pre
        pre = pre + a

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

L_hi = 1
L_lo = 2

for _ in range(int(input())-1):
    L_hi, L_lo = L_hi+L_lo, L_hi
print(L_hi)

Submission status: Accepted

Solution code:
N = int(input())

l = [0] * (N + 1)
l[0] = 2
l[1] = 1

for i in range(N + 1):
    if i == 0 or i == 1:
        continue
    else:
        l[i] = l[i - 2] + l[i - 1]

print(l[N])

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    if(N==1):
        print(1)
        return
    K=0
    L=2
    M=1
    for i in range(N-1):
        K=L+M
        L=M
        M=K
    print(K)

if(__name__=="__main__"):
    main()

Submission status: Accepted

Solution code:
input_num = int(input())

ans_list = [2,1]

for n in range(input_num - 1):
    num = ans_list[-1] + ans_list[-2]
    ans_list.append(num)


print(ans_list[-1])

Submission status: Accepted

Solution code:
N = int(input())


def fibn(a, b, k, n):
    if k < n:
        return fibn(b, a+b, k+1, n)
    else:
        return a+b
if N == 1:
    print(1)
else:
    print(fibn(2,1,2,N))

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    print(1)
else:
    l = 2
    r = 1
    for i in range(N - 1):
        L = l + r
        l = r
        r = L
    print(L)

Submission status: Accepted

Solution code:
N = int(input())

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    sub = [2, 1]
    for i in range(N - 3):
        if i % 2:
            sub[0] = sum(sub)
        else:
            sub[1] = sum(sub)
    if N % 2:
        print(sub[0] + 2 * sub[1])
    else:
        print(sub[1] + 2 * sub[0])

Submission status: Accepted

Solution code:
N= int(input())
a = [0 for i in range(87)]
a[0] = 2
a[1] = 1
for x in range(2,87):
    a[x] = a[x-2]+a[x-1]

print(a[N])

Submission status: Accepted

Solution code:
import numpy as np

def L_n(num):
    if num==0:
        return 2
    elif num==1:
        return 1
    else:
        M = np.array([[1,1],[1,0]])
        V = np.array([[1],[2]])
        for i in range(num-1):
            V = np.dot(M,V)
        return V[0][0]

if __name__ == '__main__':
    IN = int(input())
    print(L_n(IN))

Submission status: Accepted

Solution code:
def lucas_number(N):
	a, b = 2,1
	for i in range(N):
		a, b = b, a+b
	print(a)

N = int(input())
lucas_number(N)

Submission status: Accepted

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

print(L[N])

Submission status: Accepted

Solution code:
import functools


@functools.lru_cache()
def f(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return f(n - 1) + f(n - 2)


print(f(int(input())))

Submission status: Accepted

Solution code:
if __name__=="__main__":
    N = int(input())+1
    i0 = 2
    i1 = 1
    if N==1:
        print(2)
    elif N==2:
        print(1)
    else:
        temp_x=i0
        temp_y=i1
        temp = 0
        i = 3
        while not i>N :
            temp = temp_x+temp_y
            temp_x = temp_y
            temp_y = temp
            i+=1
        print(temp)

Submission status: Accepted

Solution code:
num = int(input())

zero = 2
one = 1

res = 0
for i in range(num-1):
    res = zero + one
    zero = one
    one = res
if num < 2:
    print(1 if num ==1 else 2)
else:
    print(res)

Submission status: Accepted

Solution code:
import numpy as np

def luka(n):
    a,b=1,2
    if n==1:
        pass
    elif n>=1:
        for _ in range(n-1):
            a,b=a+b,a
    
    print(a)
    

def main():
    N=int(input())

    luka(N)

if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
num = list(map(int, input().split()))
a = [2,1]
for i in range(86):
 temp = a[i] + a[i+1]
 a.append(temp)

ans = int(num[0])
print(a[ans])

Submission status: Accepted

Solution code:
N = int(input())

L = []
L.append(2)
L.append(1)

for n in range(N-1):
    L.append(L[n]+L[n+1])

print(L[N])

Submission status: Accepted

Solution code:
n = int(input())
l0 = 2
l1 = 1
if (n>=2):
    for i in range(n-1):
        l2 = l0 + l1
        l0 = l1
        l1 = l2
elif n == 0:
    l2 = 2
elif n == 1:
    l2 = 1
print(l2)

Submission status: Accepted

Solution code:
n = int(input())

a = [0 for i in range(n+1)]
a[0] = 2
a[1] = 1
for i in range(n+1)[2:n+1] :
    a[i] = a[i-1] + a[i-2]

print(a[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
a1 = 2
a2 = 1
flag = 1
for i in range(0, n):
    if flag == 1:
        a1 = a1 + a2
        flag = 0
    else:
        a2 = a1 + a2
        flag = 1

if flag == 1:
    print(a1)
else:
    print(a2)

Submission status: Accepted

Solution code:
N = int(raw_input())
a = 2 
b = 1 
na = None
nb = None
for i in range(N-1):
    na = b 
    nb = a + b 
    a = na
    b = nb
print(b)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
def L(n):
    a = 2
    b = 1
    res = 1
    for i in range(n - 1):
        res = 0
        res += a + b
        a = b
        b = res
    return res
print(L(int(input())))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""abc079_b"""

import sys
import pprint
import re

import itertools
pp = pprint.PrettyPrinter(indent=2)

def main():
    """Main function."""
    n = int(input())

    l = [2,1]

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


if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
N = int(input())
if N==1:
  import sys
  print(1)
  sys.exit()
  
ans = [0]*(N+1)
ans[0] = 2
ans[1] = 1
for i in range(2,N+1):
  ans[i]=ans[i-1]+ans[i-2]
print(ans[N])

Submission status: Accepted

Solution code:
N = int(input())

L0 = 2
L1 = 1
L2 = 3
if N == 0:
    print(L0)
elif N==1:
    print(L1)
else:
    ans = {}
    ans[0] = L0
    ans[1] = L1
    for i in range(2,N+1):
        ans[i] = ans[i-1]+ans[i-2]
    print(ans[N])

Submission status: Accepted

Solution code:
a = int(input())

L = [2,1]
if a == 0:
    print(2)
elif a == 1:
    print(1)
else:
    for x in range(2,a+1):
        L.append(L[x-1]+L[x-2])
    print(L[a])

Submission status: Accepted

Solution code:
N=input()

L0=2
L1=1
L=0

if N==1:
	print L1
else:
	for i in range(N-1):
		L=L0+L1
		L0=L1
		L1=L
	print L

Submission status: Accepted

Solution code:
q = [2,1]

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

Submission status: Accepted

Solution code:
n = int(input())

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

print(r[-1])

Submission status: Accepted

Solution code:
N = int(input())

L = [2,1]

for n in range(N-1):
    L.append(L[n]+L[n+1])

print(L[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
def solve(N):
    if N == 1: return 1
    l = [0] * (N+1)
    l[0] = 2
    l[1] = 1
    for i in range(2, N+1):
        l[i] = l[i-1] + l[i-2]
    return l[N]
print(solve(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

def luka(n):
    luka_memo = [-1 for i in range(87)]
    luka_memo[0] = 2
    luka_memo[1] = 1
    for i in range(2,n+1):
        luka_memo[i] = luka_memo[i-1] + luka_memo[i-2]
    return luka_memo[n]

print(luka(N))

Submission status: Accepted

Solution code:
n = int(input())

a0 = 2
a1 = 1

if n == 0:
  print(a0)
elif n == 1:
  print(a1)
else:
  for _ in range(n-1):
    tmp = a1
    a1 += a0
    a0 = tmp
  print(a1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    num = [0] * 87
    num[0] = 2
    num[1] = 1
    for i in range(2, 87):
        num[i] = num[i-2] + num[i-1]

    print(num[N])

main()