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: Runtime Error

Solution code:
n = int(input())
cnt = 0

def lucas(n, ans1, ans2):
    for _ in range(n-1):
        ans = ans1 + ans2
        ans1 = ans2
        ans2 = ans
    return ans

print(lucas(n, 2, 1))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
l_2 = 2
l_1 = 1

for _ in range(1,n):
  l_now = l_1 + l_2
  l_2 = l_1
  l_1 = l_now
print(l_now)

Submission status: Runtime Error

Solution code:
fn main() {
    let n: i64 = read();
    let ans = lucas(n);
    println!("{}", ans);
}

fn lucas(n: i64) -> i64 {
    if n == 0 { 2 }
    else if n == 1 { 1 }
    else {
        lucas(n-1) + lucas(n-2)
    }
}

// 以下関数

use std::io::*;
use std::str::FromStr;
pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub const MOD: u64 = 10e9 as u64 + 7;

pub fn is_prime(n: i32) -> bool {
    if n < 2 {
        return false;
    } else if n == 2 {
        return true;
    }
    let mut i = 2;
    while i * i < n {
        if n % i == 0 {
            return false;
        } else {
            i += 1;
            continue;
        }
    }
    true
}

pub fn lcm(mut n: i32, mut m: i32) -> i32 {
    n = if n > m { m } else { n };
    m = if n > m { n } else { m };
    let mut i = n;
    while i % m != 0 {
        i += n;
    }
    i
}

pub fn abs(n: i32) -> i32 {
    if n >= 0 {
        n
    } else {
        -n
    }
}

pub fn max(n: i32, m: i32) -> i32 {
    if n >= m {
        n
    } else {
        m
    }
}

pub fn min(n: i32, m: i32) -> i32 {
    if n <= m {
        n
    } else {
        m
    }
}

Submission status: Runtime Error

Solution code:
fn main() {
    let n: i32 = read();
    let ans = lucas(n);
    println!("{}", ans);
}

fn lucas(n: i32) -> i32 {
    if n == 0 { 2 }
    else if n == 1 { 1 }
    else {
        lucas(n-1) + lucas(n-2)
    }
}

// 以下関数

use std::io::*;
use std::str::FromStr;
pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub const MOD: u64 = 10e9 as u64 + 7;

pub fn is_prime(n: i32) -> bool {
    if n < 2 {
        return false;
    } else if n == 2 {
        return true;
    }
    let mut i = 2;
    while i * i < n {
        if n % i == 0 {
            return false;
        } else {
            i += 1;
            continue;
        }
    }
    true
}

pub fn lcm(mut n: i32, mut m: i32) -> i32 {
    n = if n > m { m } else { n };
    m = if n > m { n } else { m };
    let mut i = n;
    while i % m != 0 {
        i += n;
    }
    i
}

pub fn abs(n: i32) -> i32 {
    if n >= 0 {
        n
    } else {
        -n
    }
}

pub fn max(n: i32, m: i32) -> i32 {
    if n >= m {
        n
    } else {
        m
    }
}

pub fn min(n: i32, m: i32) -> i32 {
    if n <= m {
        n
    } else {
        m
    }
}

Submission status: Runtime Error

Solution code:
n = int(input())
a = 2
b = 1

for i in range(n-1):
    c = a+b
    temp = b
    b = c
    a = temp

print(c)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sympy as sym
N = 5
A = [sym.lucas(x) for x in range(N)]
print(A[N])

Submission status: Runtime Error

Solution code:
x = ['+++', '++-', '+-+', '+--', '-++', '-+-', '--+', '---']
a = input()
for i in range(8):
    ans = a[0] + x[i][0] + a[1] + x[i][1] + a[2] + x[i][2] + a[3]
    if eval(ans) == 7:
        print(ans + '=7')
        break

Submission status: Runtime Error

Solution code:
n = int(input())

i0 = 2
i1 = 1
for i in range(n-1):
    ans = i0+i1
    i0 = i1
    i1  = ans
print(ans)

Submission status: Runtime Error

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

for i in range(2,86):
    new = Num[i-1] + Num[i-2]
    Num.append(new)

ans = Num[n]
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
L=[0 for _ 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+1])

Submission status: Runtime Error

Solution code:
N = int(input())

l = [1, 2]

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

Submission status: Runtime Error

Solution code:
n=int(input())
l=[0]*n+1
l[0]=2
l[1]=1

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin

n = int(stdin.readline().rstrip())

li = [0]*86

li[0] = 2
li[1] = 1

for i in range(2,86):
    li[i] = li[i-1] + li[i-2]

print(li[n])

Submission status: Runtime Error

Solution code:
l_0 = 2
l_1 = 1
A = int(input())
if 　A == 0:
  print(l_0)
elif A == 1:
  print(l_1)
else:
  for i in range(1,A+1):
    if i%2 != 0
	    l_1 = l_0 + L_1 
    else:
      l_0 = l_0 + L_1

Submission status: Runtime Error

Solution code:
N = int(input())
L_2 = 2
L_1 = 1
for i in range(N-1):
  K = L_1+L_2
  L_2 = L_1
  L_1 = K
print(K)

Submission status: Runtime Error

Solution code:
N = int(input())
L_2 = 2
L_1 = 1
p = 0
for i in range(N-1):
  K = L_1+L_2
  L_2 = L_1
  L_1 = K
print(K)

Submission status: Runtime Error

Solution code:
N = int(input())
L_2 = 2
L_1 = 1
p = 0
for i in range(2,N+1):
  K = L_1+L_2
  L_2 = L_1
  L_1 = K
print(K)

Submission status: Runtime Error

Solution code:
#  ABC 079: B – Lucas Number
n = int(input())

l0 = 2
l1 = 1

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

print(l)

Submission status: Runtime Error

Solution code:
#  ABC 079: B – Lucas Number
n = int(input())

l0 = 2
l1 = 1

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

print(l)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
L0 = 2
L1 = 1

for _ in range(N-1):
    L = L1 + L0
    L0 = L1
    L1 = L
print(L)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
for i in range(N):
    if i == 0:
        memo.append(2)
    elif i == 1:
        memo.append(1)
    else:
        memo.append(memo[i-1] + memo[i-2])

if N == 1:
    print(1)
else:
    print(memo[N - 1] + memo[N - 2])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
def Lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else
        return Lucas(n - 1) + Lucas(n - 2)
print(Lucas(n))

Submission status: Runtime Error

Solution code:
n = int(input())
l_i_1 = 2
l_i_2 = 1
while n>=2:
  l_i = l_i_1 + l_i_2
  n -= 1
  l_i_1= l_i_2
  l_i_2 = l_i
print(l_i)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#2019/10/12
N = int(open(0).read())
L0 = 2
L1 = 1
for i in range(N-1):
    L2 = L1 + L0
    L1, L0 = L2, L1
    #print(i, L2)
print(L2)

Submission status: Runtime Error

Solution code:
memo = {}
def L(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    elif n in memo:
        return memo[n]
    memo[n] = L[n-1]+L[n-2]
    return memo[n]
print(L(int(input())))

Submission status: Runtime Error

Solution code:
memo = {}
def L(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    elif n in memo:
        return memo[n]
    memo[n] = memo[n-1]+memo[n-2]
    return memo[n]
print(L(int(input())))

Submission status: Runtime Error

Solution code:
n = int(input())
l=[0]*100
l[0]=2
l[1]=1
def ryuka(x):
    r = 0
    for i in range(2,x+1):
        l[i]=l[i-1]+l[i-2]
    return l[i]
print(ryuka(n))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
L_forward = 2
L_backward = 1
for i in range(2, N+1):
    L = L_forward + L_backward
    L_forward = L_backward
    L_backward = L
print(L)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
l=[0]*n

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

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

Submission status: Runtime Error

Solution code:
num = list(range(86))
num[0] = 2
num[1] = 1

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

print(num[int(input())])

Submission status: Runtime Error

Solution code:
N = int(input())
i = 2
m = 2
n = 1
ans = 0
while True:
  ans = m + n
  if(i == N):
    break
  k = m
  m = ans
  n = k
print(l[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())

a =[0]*86
a[0] = 2
a[1] = 1

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

print(a[N] )

Submission status: Runtime Error

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

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

print(L[i])

Submission status: Runtime Error

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 - 2] + L[i - 1]

print(L[i])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
tmp1 = 2
tmp2 = 1
for i in range(n-1):
    luc = tmp1 + tmp2
    tmp1,tmp2 = tmp2,luc

print(luc)

Submission status: Runtime Error

Solution code:
def ryuka(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1

    return ryuka(n-1) + ryuka(n-2)
print(ryuka(n))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
L_i2 = 2
L_i1 = 1
for n in range(N-1):
  L_i = L_i1 + L_i2
  L_i2 = L_i1
  L_i1 = L_i
print(L_i)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
#動的計画法

N = int(input())
Ni_2 = 2
Ni_1 = 1

for i in range(2, N + 1):
    Ni = Ni_1 + Ni_2
    Ni_2 = Ni_1
    Ni_1 = Ni
print(Ni)

Submission status: Runtime Error

Solution code:
def lucas(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return lucas(n-1)+lucas(n-2)
n= int(input())

l=((1+math.sqrt(5))/2)**n+((1-math.sqrt(5))/2)**n
print(int(l))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
K = []
S = 0
ans = 0
J = []
for i in range(N):
  K.append(list(map(int,input().split())))
for i in range(N):
  for j in range(M):
    S += K[i][j]*B[j]
  S = S + C
  J.append(S)
for i in range(N):
  if J[i] >0:
    ans += 1
  else:
    ans += 0
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
L = [ 0 ] * 86

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

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

print (L[N])

Submission status: Runtime Error

Solution code:
N = int(input())
L = [ 0 ] * 86

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

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

print (L[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())

if n = 0:
  print(2)
  exit()
if n = 1:
  print(1)
  exit()

xx = 2
x = 1
for i  in range(n-1):
  ans = xx + x
  xx = x
  x = ans

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

if N == 0:
    print(2)
elif N == 1:
    print(1)
    exit()

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

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    la = 2
    lb = 1
    for _ in range(N - 1):
        lc = la + lb
        la = lb
        lb = lc
    print(lc)


main()

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(tdin.readline().rstrip())
Lucas_number = [0]*(N+1)
Lucas_number[0] = 2
Lucas_number[1] = 1
for i in range(2,N+1):
    Lucas_number[i] = Lucas_number[i-1] + Lucas_number[i-2]
print(Lucas_number[N])

Submission status: Runtime Error

Solution code:
from sys import stdin
N = (tdin.readline(),rstrip())
Lucas_number = [0]*(N+1)
Lucas_number[0] = 2
Lucas_number[1] = 1
for i in range(2,N+1):
    Lucas_number[i] = Lucas_number[i-1] + Lucas_number[i-2]
print(Lucas_number[N])

Submission status: Runtime Error

Solution code:
N = int(input())
pre2 = 2
pre1 = 1
for i in range(2,N+1):
    l = pre2 + pre1
    pre2,pre1 = pre1,l
else:print(l)

Submission status: Runtime Error

Solution code:
input(); a = sorted(map(int, input().split()), reverse=True)
print(sum(a[0::2])-sum(a[1::2]))

Submission status: Runtime Error

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

if n == 1:
    print(1)

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

Submission status: Runtime Error

Solution code:
N = int(input())
L = [0] * 86  # 86は制約から
L[0] = 2
L[1] = 1
if N >= 2:
	for i in range(2, N + 1):
		L[i] = L[i - 1] + L[i - 2]
print(L[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(raw_input())

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
if n==0:
    print(2)
elif n==1:
    print(1)
else:
    temp1 = 2
    temp2 = 1
    ans = 0
    for i in range(n-1):
        ans = temp1 + temp2
        temp1 = temp2
        temp2 = ans
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

def calcLucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    return calc(n-1) + calc(n-2)

print(calcLucas(n))

Submission status: Runtime Error

Solution code:
n = int(input())
LUKAS = [0, 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, (71)425730551631123, 688846502588399, 1114577054219522, 1803423556807921, 2918000611027443, 4721424167835364, 7639424778862807, 12360848946632171, 20000273725560978, 32361122672259149, 52361396397820127, 84722519070079276, 137083915467899403, 221806434537978679, 358890350005878082, 580696784543856761, 939587134549734843]

print(LUKAS[n])

Submission status: Runtime Error

Solution code:
N = int(input())

L0 = 2
L1 = 1

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

print(L)

Submission status: Runtime Error

Solution code:
def luca(n):
  if n == 2:
    return 1
  elif n == 1:
    return 2
  luca(n) = luca(n-1) + luca(n-2)
  return

print(luca(int(input()))

Submission status: Runtime Error

Solution code:
def memoize(f):
  cache={}
    def helper(*args):
      if args not in cache:
        cache[args] = f(*args)
        return cache[args]
      return helper

@memoize
def ans(N):
  if N==0:
    return 1
  elif N==1:
    return 2
  else:
    return ans(N-1)+ans(N-2)
  
N=int(input())
print(ans(N))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())

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

print(l[n])

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
L0 = 2
L1 = 1
for _ in range(N-1):
    L = L0 + L1
    L0 = L1
    L1 = L
print(L)

Submission status: Runtime Error

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

print(l)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
l = [10^18]
l[0] = 2
l[1] = 1
if n == 0 or n == 1:
  print(l[n])
for i in n:
  l.append(l[i - 1] + l[i -2])
print(l[n])

Submission status: Runtime Error

Solution code:
n = int(input())
l = []
l[0] = 2
l[1] = 1
if n == 0 or n == 1:
  print(l[n])
for i in n:
  l[i] = l[i - 1] + l[i -2]
print(l[n])

Submission status: Runtime Error

Solution code:
def lucas(n):
  if n == 0:
    return 2
  elif n == 1:
    return 1
  else:
    a = lucas(n-1)
    b = lucas(n-2)
    c = a+b
    return(c)
print(lucas(n))

Submission status: Runtime Error

Solution code:
def get_new_lucas(l_i_1, l_i_2):
    """
    get a new Lucas number L_i

    l_i_1: L_(i-1),
    l_i_2: L_(i-2)
    """
    return l_i_1 + l_i_2


def main():
    n = int(input())
    tmp_l_i_1 = 1
    tmp_l_i_2 = 2
    for i in range(1, n):
        if i == 1:
            new_lucas_num = get_new_lucas(tmp_l_i_1, tmp_l_i_2)
        else:
            new_lucas_num = get_new_lucas(tmp_l_i_1, tmp_l_i_2)
        tmp_l_i_2 = tmp_l_i_1
        tmp_l_i_1 = new_lucas_num
        
    print(new_lucas_num)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
l0 = 2
l1 = 1
if n == 0:
    print(l0)
    return
if n == 1:
    print(l1)
    return

l_prev = l0
l_next = l1

i = 2
while True:
    l_new = l_prev + l_next
    if n == i:
        print(l_new)
        break
    l_prev = l_next
    l_next = l_new
    i += 1

Submission status: Runtime Error

Solution code:
n = int(input())

l_prev = l0
l_next = l1

l_new = 0
for i in range(2, n+1):
    l_new = l_prev + l_next
    l_prev = l_next
    l_next = l_new
print(l_new)

Submission status: Runtime Error

Solution code:
n = long(input())
l0 = 2L
l1 = 1L
if n == 0:
    print(l0)
if n == 1:
    print(l1)

l_prev = l0
l_next = l1

l_new = 0L
for i in range(2, n+1):
    l_new = l_prev + l_next
    l_prev = l_next
    l_next = l_new
print(l_new)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
init = np.expand_dims(np.array([2, 1]), 0)
to_next = np.array([
    [1, 1],
    [1, 2],
])
for i in range(n // 2):
    init = init @ to_next
print(init[0][n & 1])

Submission status: Runtime Error

Solution code:
n=int(input())
def lucas(n):
	if n=0:
		return 2
	if n=1:
		return 1
	if n>1:
		return lucas(n-1)+lucas(n-2)
print(lucas(n))

Submission status: Runtime Error

Solution code:
n = int(input())-1
a, b = 2, 1
if(n==0):
    print(2)
elif(n==1):
    print(1)
while(n):
    c = a + b
    a = b
    b = c
    n -= 1
print(c)

Submission status: Runtime Error

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

answer = []
for p in range(2, 7):

    for i in range(1, x):
        test = i**p
        if test > x:
            answer.append((i-1)**p)
            break
        elif test == x:
            answer.append(i**p)
            break

print(max(answer))

Submission status: Runtime Error

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

fib(int(input())-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
a=np.zeros(87)
a[0]=2
a[1]=1
N=int(input())
for i in range(2,N+1):
    a[i]=a[i-1]+a[i-2]
print(int(a[i]))

Submission status: Runtime Error

Solution code:
import time

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[i]

def main():
    N = input()
    if(N == 0):
        print(2)
    else:
        print(fib(int(N)+1))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import time

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[i]

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())

ryuka = [0]*86
ryuka[0] = 2
ryuka[1] = 1

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

ryuka = culc_ryuka(N, ryuka)
print(ryuka[N])

Submission status: Runtime Error

Solution code:

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())

Lx = 2
Ly = 1

if N == 1:
    print(Ly)
else:
    for i in range(N-1):
        tmp = Lx + Ly
        Lx = Ly
        Ly = tmp

print(tmp)

Submission status: Runtime Error

Solution code:
N = int(input())
l_im2, l_im1 = 2, 1
for i in range(2, N + 1):
	l_i = l_im1 + l_im2
	l_im1, l_im2 = l_i, l_im1
print(l_i)

Submission status: Runtime Error

Solution code:
# N = list(map(int, input().split()))
# print(N[0], N[1], N[2])
# print(N[1])
# print(N[2])

N = int(input())
i = 2
a = 2
b = 1

while i <= N:
  c = a + b
  a = b
  b = c
  i = i + 1

print(c)

Submission status: Runtime Error

Solution code:
N = int(raw_input())
lis = [None]*86
lis[0] = 2
lis[1] = 1
for i in xrange(84):
	lis[i+2] = lis[i-1] + lis[i]
print lis[N-1]

Submission status: Runtime Error

Solution code:
N = raw_input()

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

print L[N]

Submission status: Runtime Error

Solution code:
N = 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: Runtime Error

Solution code:
N = int(input())
pre = 1
luca = 3
if N == 2:
  print(4)
  break
elif N == 1:
  print(1)
  break
elif N == 0:
  print(2)
  break
else:
  for i in range(N - 2):
    temp = luca
    luca = pre + luca
    pre = temp
    
  print(luca)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long int ulli;
typedef long long int lli;
#define pb(a) push_back(a)
#define pbb(a) pop_back(a)  
#define ph(a) push_heap(a.begin(), a.end())
#define pph(a) pop_heap(a.begin(), a.end())
#define si set<int>
#define sl set<long>
#define sc set<char>
#define pii pair<int, int>
#define pll pair<long, long>
#define pdd pair<double, double>
#define TC(t) while(t--)
#define FORA(a,b,c) for ((a) == (b); (a) < (c); (a) ++)
#define FORB(a,b,c) for ((a) == (b); (a) <= (c); (a) ++)
#define FORC(a,b) for ((a) == (b); (a) > 0; (a)--)
#define FORD(a,b) for ((a) == (b); (a) >= 0; (a)--)                         
#define WM(a) while(a--)
#define WP(a) while(a++)
#define print(data) cout << data << endl
#define tin(a) cin >> a
#define ttin(a,b) cin >> a >> b
#define tttin(a,b,c) cin >> a >> b >> c
#define maxheap(a) make_heap(a.begin(),a.end())
#define fixp(a)  cout << fixed << setprecision(a);
#define RM(a,n) a.erase(remopricee(a.begin(), a.end(), n),a.end())
#define MOD 1000000007
ll prime[] = {2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47};
inline int gmx (int a, int b){
	return a > b ? a : b;
}
inline int gmm (int a, int b){
	return a < b ? a : b;
}
inline ll get_gcd(ll a, ll b){
    ll rem = 0;
    while( b != 0){
        rem = a % b;
        a = b; 
        b = rem;
    }
    return a;   
}
ll fastexp (ll base, ll exp){
	ll res = 1;
	if (exp == 0) return 1LL;
	while(exp){
		if(exp&1) res = (res*base)%MOD;
		res = (res+MOD)%MOD;
		base = (base*base)%MOD;
		base = (base+MOD)%MOD;
		exp >>= 1;
	}
	return (ll)res;
}
struct compare {
    bool operator()(const std::string& first, const std::string& second) {
        return first.size() < second.size();
    }
};
void Verdict_Check(){
	ifstream A("my_output.txt");
	ifstream B("code_output.txt");
	
	int c1=0,c2=0;
	bool WA = false;
	string str;
	while(getline(A,str)){
		c1++;
	}
	while(getline(B,str)){
		c2++;
	}
	A.close();
	B.close();
	ifstream AA("my_output.txt");
	ifstream BB("code_output.txt");
	if (c1 != c2){
		WA = true;
	}else{
		string s,ss;
		while(getline(AA,s) && getline(BB,ss)){
			if(s != ss){
				WA = true;
			}
		}
	}
	if (WA){
		cout << "Wrong answer!!!" << endl;
	}else{
		cout << "All test cases are passed!!!" << endl;
	}
	AA.close();
	BB.close();
}
int N;
ll a[86+5];
int main(){
	int A[10000];
	//freopen("a.in","r",stdin);
	//freopen("my_output.txt","a", stdout);
	clock_t tStart = clock();
	scanf("%d",&N);
	a[0] = 2LL;a[1] = 1LL;
	for (int i = 2; i <= N; i ++)a[i] = a[i-1] + a[i-2];
	printf("%lld\n",a[N]);
	//freopen("CON", "w", stdout);
	//Verdict_Check();
	// printf("Time taken: %.7fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys

N = int(input())

L0=2
L1=1

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

Submission status: Runtime Error

Solution code:
import time

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[i]

a = input()
print(fib(int(a)+1))

Submission status: Runtime Error

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

z=str(z)
print z