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:
n = int(input())
l0 = 2
l1 = 1
if n == 0:
    print(l0)
elif n == 1:
    print(l1)
elif n>= 2:
    ll = [l0, l1] + [0 for _ in range(n-1)]
    for i in range(2,n+1):
        ll[i] = ll[i-1] + ll[i-2]
    print(ll[n])

Submission status: Accepted

Solution code:
n = int(input())
memo = [2, 1]
if n == 1:
    print(memo[n])
    exit()
else:
    for i in range(1,n):
        tmp = memo[1]
        memo[1] = memo[0] + tmp
        memo[0] = tmp

print(memo[1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

N = int(input())
l=[-1]*(N+1)

def lyuka(x):
  if l[x] != -1:
    return l[x]
  if x == 0:
    return 2
  if x == 1:
    return 1
  lyu = lyuka(x-1) + lyuka(x-2)
  l[x] = lyu
  return lyu

print(lyuka(N))

Submission status: Accepted

Solution code:
N = int(input())

if N == 1:
  print(1)
  exit()

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]

print(L[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[-1])

Submission status: Accepted

Solution code:
def inp():
    return(int(input()))


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


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


n = inp()
print(lucas(n))

Submission status: Accepted

Solution code:
N = int(input())

n = [0] * (N+1)
for i in range(N+1):
    if i == 0:
        n[i] = 2
    elif i == 1:
        n[i] = 1
    else:
        n[i] = n[i-1] + n[i-2]

print(n[N])

Submission status: Accepted

Solution code:

N=int(input())
ans=[None]*(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())

a =2
b =1

if N == 1:
    print(b)
else:
    for _ in range(1,N):
        c = b + a
        a = b
        b = c
    print(c)

Submission status: Accepted

Solution code:
N = int(input())

a =2
b =1

if N == 1:
    print(b)
else:
    for _ in range(1,N):
        c = b + a
        a = b
        b = c

    else:
        print(c)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
    print(1)
else:
    l1=2
    l2=1
    for i in range(n-1):
        l3=l1+l2
        l1=l2
        l2=l3
    print(l2)

Submission status: Accepted

Solution code:
from functools import lru_cache

N = int(input())

@lru_cache(maxsize=None)
def luca(N):
  if N>=2:
    return luca(N-2)+luca(N-1)
  if N==1:
    return 1
  if N==0:
    return 2
  
print(luca(N))

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
num2 = 2
num1 = 1
num = 1
tmp = 0
i = 2

while i <= N:
    num = num1 + num2
    tmp = num
    num2 = num1
    num1 = tmp
    i += 1
print(num)

Submission status: Accepted

Solution code:
n=int(input())
l1,l2=2,1

for i in range(n):
  l1,l2=l2,l1+l2
  
print(l1)

Submission status: Accepted

Solution code:
n = int(input())
l0 = 2
l1 = 1
l = 0
if n == 1:
    print(l1)
else:
    for i in range(2, n + 1):
        l = l1 + l0
        l0 = l1
        l1 = l
    print(l)

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[-1])

Submission status: Accepted

Solution code:
n = int(input())

l = [0] * 100
l[0] = 2
l[1] = 1

if n == 0 or n == 1:
    print(l[n])
if n>=2:
    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())
l0=2
l1 = 1
l = l0 + l1
for i in range(n-2):
    l0 = l1
    l1 = l
    l = l0 + l1
if n==1:
  print(l1)
else:
  print(l)

Submission status: Accepted

Solution code:
n=int(input())
lo=2
li=1
cou=0
import sys
if n==1:
    print(1)
    sys.exit()
if n==2:
    print(3)
    sys.exit()

for  i in range(n-1):

    cou=lo+li
    lo=li
    li=cou
   

print(cou)

Submission status: Accepted

Solution code:
import sys
import math
import itertools

n = int(input())
lucas = [
    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(lucas[n-1])

Submission status: Accepted

Solution code:
n=int(input())
 
a=2
b=1
s=0
 
if n==1:
  s=1
  n=2
 
for i in range(n-1):
  nn = a+b
  ans=nn
  a=b
  b=nn
 
if s==1:
  ans = 1
 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#A,B,C=map(float,input().split())
#a,b,c=map(int,input().split())
N=int(input())
Lm=2
Ln=1
Lo=2
if N==0:
	print(2)
elif N==1:
	print(1)
else:
	for i in range(N-1):
		Lo=Lm+Ln
		Lm=Ln
		Ln=Lo
	print(Lo)

Submission status: Accepted

Solution code:
n = int(input())
lucas = [2, 1]
for i in range(2, 100):
    lucas.append(lucas[i - 1] + lucas[i - 2])
print(lucas[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:
n = int(input())
l1 = 2
l2 = 1

for i in range(1, n):
    l1, l2 = l2, l1 + l2

print(l2)

Submission status: Accepted

Solution code:
N = int(input())
L = [-1] * 87
L[0] = 2
L[1] = 1

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

print(L[N])

Submission status: Accepted

Solution code:
n = int(input())

dp = [2, 1]
if n >= 2:
    for _ in range(n-1):
        dp.append(dp[-1] + dp[-2])

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())

a, b = 2, 1

for i in range(n):
    a, b = b,a+b

print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Ryuka(n):
    L = [2,1]
    for i in range(n-1):
        L.append(L[len(L)-1]+L[len(L)-2])

    return L[len(L)-1]

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

print(ans)

Submission status: Accepted

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

print(l[-1])

Submission status: Accepted

Solution code:
n = int(input())

l = [0]*87

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

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

print(l[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
l=[2,1]#i=1まで入っている
for i in range(n-1):
    l.append(l[-2]+l[-1])
print(l[-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import copy

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

Submission status: Accepted

Solution code:
N = int(input())

List = [2, 1]

for i in range(2, 88):
    List.append(List[i-1]+List[i-2])

print(List[N])

Submission status: Accepted

Solution code:
import sys
import math
import bisect

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May 14 01:22:46 2020

@author: shinba
"""

L = [2,1]

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

print(L[int(input())])

Submission status: Accepted

Solution code:
from functools import lru_cache

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

N = int(input())

print(lucas(N))

Submission status: Accepted

Solution code:
n=int(input())
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]
print(l[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
x = int(input())
lucasList = [2,1]
if x!=1:
    for i in range(2,x+1):
        lucasList.append(lucasList[i-1]+lucasList[i-2])
print(lucasList[x])

Submission status: Accepted

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

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:
n = int(input())
L = [2, 1]
for i in range(2, n + 1):
    L.append(L[i-1] + L[i-2])
print(L[-1])

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int):
    L = [2, 1]
    for _ in range(100):
        L.append(L[-1]+L[-2])
    return L[N]


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    print(solve(N))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

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:
A=int(input())
b0=2
b1=1
save=0
for i in range(A-1):
    save=b1
    b1=b0+b1
    b0=save
print(b1)

Submission status: Accepted

Solution code:
A = [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(A[int(input())])

Submission status: Accepted

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

import fractions
import copy
import bisect
import math
import numpy as np
import itertools
from itertools import combinations_with_replacement
#import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
from operator import itemgetter
from sys import stdin
#input = sys.stdin.readline#こっちの方が入力が早いが使える時に使っていこう
from operator import mul
from functools import reduce
from collections import Counter
#from collections import deque

#input = stdin.readline


j=0
k=0
n=3
r=1
a=[0]
#n=int(input())
#r=int(input())
#print(M)
#A=int(input())
#B=int(input())
#print(N)
"1行1つの整数を入力を取得し、整数と取得する"


#number_list=list(map(int, input().split(" ")))#数字の時
#print(number_list)
"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#メモ
for i in number_list:#こっちの方がrage使うより早いらしい
    print(number_list[i-1])#

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''
#array=[input().split()for i in range(N)]
#print(type(array[0][0]))
#print(array)
"正方行列にstr型の値を入力"
'''

#brray=[list(map(int, input().split(" ")))for i in range(N)]
#print(type(brray[0][0]))
#print(brray)
'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"
#以下に別解を記載
#N, M = [int(i) for i in input().split()]
'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''




#s=input()
#a=[int(i) for i in s]
#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ
#intを取ると文字列分解に使える
'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()#str style 何個でもいけることが多い
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''


#a= stdin.readline().rstrip()
#print(a.upper())
"aという変数に入っているものを大文字にして出力"


#a,b=map(int, input().split())  #int style 複数数値入力　「A B」みたいなスペース空いた入力のとき

#なんかうまく入力されるけど
#a=[[int(i) for i in 1.strip()]for 1 in sys.stdin]
#a = [[int(c) for c in l.strip()] for l in sys.stdin]]
#print(a)
#複数行の数値を入力して正方行列を作成


##############################################################################################
##############################################################################################
#under this line explains example calculation



'''
コンビネーションの組み合わせの中身を出力する形式
for i in itertools.combinations(brray, 2)
combinationsをpermutationsにすれば順列になる
今回なら(abc133B)
入力
1 2
5 5
-2 8
出力
[[1, 2], [5, 5], [-2, 8]]
もちろん一次元リストでも使えるし
何よりiもリストのように使えるので便利
'''

#nCr combination
'''
def cmb(n,r):
    #When n < r , this function isn't valid
    r= min(n-r,r)
    #print(n,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n-r, -1))
    #flochart mul(n,n-1)=x
    #next     mul(x,n-2)........(n-r+1,n-r)
    #mul read a,b and returns a*b

    under = reduce(mul, range(1, r+1))
    #print(over, under)
    #reduce is applied mul(1,2)=2
    #next   mul(2,3)=6
    #next   mul(6,4)=4.........last(r!,r+1)=r+1!

    return over // under
    #// is integer divide
    #calc example 5C2
    #over=5*4*3
    #under=3*2*1
a = cmb(n, r)
#print(a)
'''

'''
import itertools
from itertools import combinations_with_replacement

combinationについて
以下の違いを意識しよう
combinations() p, r 長さrのタプル列、ソートされた順で重複なし

combinations_with_replacement() p, r 長さrのタプル列、ソートされた順で重複あり


使用例 　　　　　　　　　　　                  出力　　
combinations('ABCD', 2)　　　　　　　　　　　　AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)　　 AA AB AC AD BB BC BD CC CD DD
'''



'''
#集計
#example
#a=[2,2,2,3,4,3,1,2,1,3,1,2,1,2,2,1,2,1]
#a=Counter(a)
for i in a.most_common(n):print(i)
#most_common()メソッドは、出現回数が多い要素順にCounterオブジェクトを並び替えます。
#引数にint型の数字nを設定した場合は、出現回数が高い上位ｎ個の要素を返します。
#何も設定しなければ、コンテナ型にあるすべての要素を出現回数の順番に並び替えたタプル型オブジェクトを返します。
#out put
#(2, 8)
 #(1, 6)
#(3, 3)
#(4, 1)
'''


#二部探索(binary search)
#A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
#print(A)
#index = bisect.bisect_left(A, 5) # 7 最も左(前)の挿入箇所が返ってきている
#A.insert(index, 5)
#print(index)
#print(A)
'''
bisect.bisect_left(a, x, lo=0, h=len(a))
引数
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)
bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。
'''

'''
素数の判定
'''


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(np.sqrt(n)) + 1):
        #sqrt(n)+1以上は考えて約数はないので却下
        if n % k == 0:
            return False
            #割り切れたらFalse
    return True


'''
npのmaxとmaximumの違い
xs = np.array([1, -2, 3])
np.max(xs, 0)
この出力は3となります．[1, -2, 3]と0の4つの数字のうち，最も大きい値を出力します．

一方で，[max(1, 0), max(-2, 0), max(3, 0)]を出力したい時があります．
その時は，numpyのmaximum関数を用います．

xs = np.array([1, -2, 3])
np.maximum(xs, 0)  # [1, 0, 3]

'''

def factorial(x, mod=10**9+7):
    # x!
    # 階乗
    # ex) factorial(5) = 120
    tmp = 1
    for i in range(1, x+1):
        tmp = (tmp * i) % mod
    return tmp
    '''
    Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large.
    But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does.
    '''


########################################################################
########################################################################
#b2=a[:]  #1次元のときはコピーはこれで良い
#print(b2)

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b3=copy.deepcopy(a)  #2次元配列はこうコピーする
#print(b3)

def main():

    w=1
    j=0
    k=0
    n=int(input())
    l=[0]*(n+1)
    l[0]=2
    l[1]=1
    for i in range(n-1):
        l[i+2]=l[i+1]+l[i]
    #print(l)
    print(l[-1])
    #r=int(input())
    #dp= [[0]*3 for i in range(5)]#列　行
    #dp用の0の入ったやつ
    #dp= [[0]*(w+1) for i in range(n+1)]#0からwまでのw+1回計算するから
    #print(dp)＃初期条件が入る分計算回数+1列分必要(この場合は判断すべきものの数)
    DP = np.zeros(w+1, dtype=int)#これでも一次元リストが作れる
    exdp=np.zeros((3,4)) # ３×４の２次元配列を生成。2次元ならこう
    #dtypeは指定しないとfloatになる
    #for i in range(n):#ちょっとした入力に便利
    #    a, b = map(int, input().split())
        #dp[i][0] += [a]
        #これだとintとlistをつなぐことになって不適
    #    dp[i] += [a]
    #    dp[i] += [b]
        #これはうまくいく
        #やり方はいろいろあるということ
    #print(dp)


    "1行1つの整数を入力を取得し、整数と取得する"
    #nl=list(map(int, input().split(" ")))#数字の時
    #print(number_list)
    "12 21 332 とか入力する時に使う"
    "1行に複数の整数の入力を取得し、整数として扱う"
    #brray=[list(map(int, input().split(" ")))for i in range(N)
    #print(brray)


    #s=input()
    #a=[int(i) for i in s]#int取るとstrでも行ける
    #print(a)
    '''
    入力
    1234
    出力
    [1, 2, 3, 4]
    '''
    pin_l=["x" for i in range(10)]#内包表記に慣れろ
    #print(pin_l)

    ls = ["a", "b", "c", "d", "e"]


    #print(ls[2:5])
    #スライスでの取得

    #print(ls[:-3])
    #一番左端から右から3番目より左まで取得

    #print(ls[:4:2])
    #スライスで1個飛ばしで取得
    #ないときは左端スタート
    #始点のインデックス番号 : 終点のインデックス番号 : スキップする数+1
    #print(ls[::2])
    '''
    lsというリストの場合に、1つ飛びの値を取得したい場合には
    ls[::2]
    のようにします。こうすると、
    ["a", "c", "d"]と出力される
    '''

if __name__ == "__main__":
    main()

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:
N = int(input())
A =[2,1]
if N < 2:
    print(A[N])
    exit()
for i in range(2,N+1):
    A.append(A[i-1]+A[i-2])
print(A[-1])

Submission status: Accepted

Solution code:
N = int(input())
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:
import sys
sys.setrecursionlimit(10000)
dp = {}
def lucas(n):
    if n in dp:
        return dp[n]
    if n == 0:
        dp[n] = 2
        return dp[n]
    if n == 1:
        dp[n] = 1
        return dp[n]
    dp[n] =  lucas(n-1)+lucas(n-2)
    return dp[n]
N = int(input())
print(lucas(N))

Submission status: Accepted

Solution code:
# import functools
N = int(input())

#for i in range(N+1):
# @functools.lru_cache()
# def L(i):
#     if i == 0:
#         return 2
#     if i == 1:
#         return 1
#     else:
#         return L(i-1) + L(i-2)
# print(L(N))


#上はfunctoolを使うもの下がいい

LL = [2,1] # リュカ数保存するリスト

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

print(LL[N])

Submission status: Accepted

Solution code:
n = int(input())

l = [2,1]

for i in range(86):
  l.append(l[-1]+l[-2])
  
print(l[n])

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
l = [2,1]
if n==1:
    print(l[1])
else:
    c = 2
    while(c<=n):
        l.append(sum(l[-2:]))
        c+=1
    print(l[-1])

Submission status: Accepted

Solution code:
N = int(input())

llucas = [2, 1]

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

print(llucas[N])

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline())

L0 = 2
L1 = 1
L = L1
Lmin = L0

if N == 1:
  print(1)
  sys.exit()
for i in range(2, N+1):

  Li = L + Lmin
  Lmin = L
  L = Li

print(Li)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()

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])

Submission status: Accepted

Solution code:
# 2020/05/08
# AtCoder Beginner Contest 079 - B

# Input
n = int(input())
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]
    
# Output
print(l[n])

Submission status: Accepted

Solution code:
def calc(n, dp):
	if dp[n]:
		return dp[n]
	if n <= 1:
		return dp[n]
	dp[n] = calc(n-1, dp) + calc(n-2, dp)
	return dp[n]

def resolve():
	n = int(input())
	dp = [None] * 87
	dp[0], dp[1] = 2, 1
	print(calc(n, dp))
resolve()

Submission status: Accepted

Solution code:
n = int(input())
lucas = [2,1]
if n == 0:
  print(2)
elif n == 1:
  print(1)
t = 2
while t <= n:
  next_lucas = lucas[-1] + lucas[-2]
  lucas.append(next_lucas)
  if t == n:
    print(next_lucas)
  t += 1

Submission status: Accepted

Solution code:
def solve(n):

    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        l0 = 2
        l1 = 1
        for i in range(2,n+1):
            l = l1 + l0
            l0 = l1
            l1 = l
        return l

if __name__ == "__main__":
    n = int(input())
    print(solve(n))

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())

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

print(memo[-1])

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**7)
rs = lambda: sys.stdin.readline().rstrip()
ri = lambda: int(rs())
rf = lambda: float(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]
rf_ = lambda: [float(_) for _ in rs().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
PI = math.pi
# endregion
@lru_cache(maxsize=None)
def f(N):
    if N == 0: return 2
    if N == 1: return 1
    return f(N - 1) + f(N - 2)
print(f(ri()))

Submission status: Accepted

Solution code:
n=int(input())
ans=0
first=1
second=3
for i in range(n-2):
    ans=first+second
    first=second
    second=ans
print(ans if n>2 else "1" if n==1 else "3")

Submission status: Accepted

Solution code:
n=int(input())
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:
n = int(input())
l0 = 2
l1 = 1
if n==1:
  print(l1)
else:
  for i in range(n-1):
    sum = l0+l1
    l0 = l1
    l1 = sum
  print(sum)

Submission status: Accepted

Solution code:
def lucas_number(n):
  l = [2, 1]
  l_i_1 = 1
  l_i_2 = 2
  if n == 1:
    return l[1]
  
  for i in range(n-1):
    tmpl = l[-1] + l[-2]
    l.append(tmpl)
    
  return l[-1]

n = int(input())
print(lucas_number(n))

Submission status: Accepted

Solution code:
N = int(input())
ans = [2,1]

for i in range(2,87):
    tmp = ans[i-2] + ans[i-1]
    ans.append(tmp)

print(ans[N])

Submission status: Accepted

Solution code:
n = int(input())
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:
n = int(input())
l = [0]*90
l[0] = 2
l[1] = 1

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

print(l[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

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

Submission status: Accepted

Solution code:

import sys
def input(): return sys.stdin.readline().strip()

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

Submission status: Accepted

Solution code:

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    a=2
    b=1
    num=0
    if n==1:
        print(b)
    else:
        for i in range(n-1):
           num=a+b
           a,b=b,a+b
        print(num)
resolve()

Submission status: Accepted

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

main()

Submission status: Accepted

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
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]
print(l[N])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)




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

    if n == 1:
        print(1)
    else:
        _x2 = 2
        _x1 = 1
        _x = 0
        for i in range(n-1):
            _x = _x2 + _x1
            _x2 = _x1
            _x1 = _x

        print(_x)


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
l = [2,1]

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