Honeycomb (Editorial)

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:

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

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

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();
  }
}