5092. Honeycomb

A bee, moving inside a honeycomb, can move as shown in the figure:

· by moves 1 and 2 – from the upper row,

· by move 3 – from the lower row.

Input. The number of hexagons n (1 ≤ n ≤ 45) in the upper row is given. The lower row contains one hexagon fewer.

Output. Print the number of ways in which the bee can reach the last cell of the upper row starting from the first cell of the same row.

Sample input	Sample output
3	2

SOLUTION

dynamic programming – Fibonacci numbers

Algorithm analysis

Number all the hexagons consecutively from left to right, top to bottom, as shown in the picture. In this numbering:

· hexagons in the upper row have odd numbers;

· hexagons in the lower row have even numbers.

If the upper row contains n hexagons, the rightmost hexagon in the upper row will have number 2n – 1.

Let f(k) denote the number of ways to reach the hexagon numbered k from the first hexagon. Since the bee needs to reach hexagon number 2n – 1, the answer to the problem will be f(2n – 1).

Now, let’s consider the transitions between hexagons.

· Let hexagon k be in the upper row (an odd number). Then the bee can reach it either from hexagon k – 2 or from hexagon k – 3. Therefore, for odd k the following recurrence holds:

f(k) = f(k – 2) + f(k – 3)

· Let hexagon k be in the lower row (an even number). In this case, there is only one possible transition – from the previous hexagon:

f(k) = f(k – 1)

To implement the recursion, we need to set the initial values:

f(1) = 1, f(2) = 1, f(3) = 1

These can be easily verified directly from the bee’s movement diagram.

Algorithm implementation

Declare an array.

#define MAX 100

int fib[MAX];

Fill the elements of the fib array in accordance with the recurrence relation.

fib[0] = 0; fib[1] = 1; fib[2] = 1;

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

if (i % 2 == 1) fib[i] = fib[i-2] + fib[i-3];

else fib[i] = fib[i-1];

Read the value n and print the answer f(2n – 1).

scanf("%d",&n);

printf("%d\n",fib[2*n-1]);

Algorithm implementation – recursion + memorization

Declare an array.

int fib[90];

Implement a recursive function f using memoization.

int f(int n)

{

if (n == 1) return 1;

if (n == 2) return 1;

if (n == 3) return 1;

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

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

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

}

The main part of the program. Read the input value n.

scanf("%d",&n);

Compute and print the answer.

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

printf("%d\n",f(2*n-1));

Java implementation

import java.util.*;

public class Main

{

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

static int f(int n)

{

if (n <= 3) return 1;

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

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

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

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Arrays.fill(fib, -1);

System.out.println(f(2*n-1));

con.close();

}

}