5091. Explosive containers

All containers in the world are divided into two categories – with or without trotyl (TNT). Only a fool would put a box with TNT on another box with TNT. Since you are not a fool (hmm ...), you know exactly that TNT explode, especially if it is on another box with TNT. You are in the room in which there are two types of boxes in a huge quantity. Suddenly, the lifter comes into the room from the hatch. It fails. It is intended to build a tower with n boxes. To estimate your chance to survive, you have to count the number of outcomes where nothing explodes.

By the way, what a reasonable person like you doing in a room with a bunch of TNT?

Input. One integer n (1 ≤ n < 45).

Output. Print the number of good outcomes.

Sample input 1	Sample output 1
1	2
Sample input 2	Sample output 2
2	3

SOLUTION

Fibonacci numbers

Algorithm analysis

Let's code the empty box with 0 and the box with TNT with 1. In the problem we must find the number of strings of length n consisting of 0 and 1, in which two ones are not adjacent. The answer to the problem will be the Fibonacci number f(n):

Example

Consider all possible towers of height n = 1, n = 2, n = 3. Each of them corresponds a sequence of 0 and 1. There are:

· two towers of height 1;

· three towers of height 2;

· five towers of height 3;

Algorithm realization

Declare the working array.

#define MAX 45

int fib[MAX];

Fill the cells of array fib according to the given recurrence.

fib[1] = 2; fib[2] = 3;

for (int i = 3; i < MAX; i++)

fib[i] = fib[i - 1] + fib[i - 2];

Read the input value of n and print the answer.

scanf("%d", &n);

printf("%d\n", fib[n]);

Algorithm realization – memorization

#include <stdio.h>

#include <string.h>

#define MAX 45

int n, fib[MAX];

int f(int n)

{

if (n == 1) return 2;

if (n == 2) return 3;

if (fib[n] != -1) return fib[n];

return fib[n] = f(n - 1) + f(n - 2);

}

int main(void)

{

scanf("%d", &n);

memset(fib, -1, sizeof(fib));

printf("%d\n", f(n));

return 0;

}

Java realization

import java.util.*;

public class Main

{

static int fib[] = new int[45];

static int f(int n)

{

if (n == 1) return 2;

if (n == 2) return 3;

if (fib[n] != -1) return fib[n];

return fib[n] = f(n-1) + f(n - 2);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Arrays.fill(fib, -1);

System.out.println(f(n));

con.close();

}

}

Python realization – list

lst = [0, 2, 3]

for i in range(3, 45):

lst.append(lst[i - 2] + lst[i - 1])

n = int(input())

print(lst[n])

Python realization – memorization

n = int(input())

dp = (n + 2) * [-1]

def fib(n):

if dp[n] != -1:

return dp[n]

dp[n] = fib(n - 1) + fib(n - 2)

return dp[n]

dp[1] = 2

dp[2] = 3

print(fib(n))