Три одиниці (Розбір)

Позначимо через $f(n)$ кількість шуканих послідовностей з $0$ та $1$ довжини $n$. Розглянемо побудову послідовності за першим символом.

Якщо на першому місці стоїть $0$, то решта частина послідовності може бути будь-якою допустимою послідовністю довжини n - 1. Отже, таких варіантів f(n - 1).

Якщо на першому місці стоїть $1$, то розглянемо можливі продовження:

• якщо на другому місці стоїть $0$, то решта n - 2 позицій утворюють довільну допустиму послідовність довжини n - 2, тобто f(n - 2) варіантів;

• якщо на другому місці стоїть $1$, то щоб не допустити три одиниці поспіль, на третьому місці обов'язково повинен стояти $0$. Після цього залишається n - 3 позиції, які можна заповнити довільною допустимою послідовністю, тобто f(n - 3) варіантів.

Таким чином, отримуємо рекурентне співвідношення:

Залишається обчислити початкові значення:

• f(1) = 2, оскільки існує дві послідовності довжини $1$: $0$ та $1$.

• f(2) = 4, оскільки існує чотири послідовності довжини $2$: $00,01,10$ та $11$.

• f(3) = 7, оскільки існує сім послідовностей довжини $3$: 000, 001, 010, 011, 100, 101 та $110$.

Приклад

Реалізація алгоритму

Оголосимо масив $f$, у якому будемо зберігати значення f(1), f(2), ..., f(n).

int f[100010];

Зчитуємо вхідне значення $n$.

scanf("%d",&n);

Ініціалізуємо базові значення масиву.

f[1] = 2; f[2] = 4; f[3] = 7;

Обчислюємо значення $f(i)$ за рекурентною формулою. Усі обчислення виконуємо за модулем $12345$.

for(i = 4; i <= n; i++)
  f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

Виводимо відповідь.

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

Реалізація алгоритму – рекурсія + запам'ятовування

Оголосимо масив $dp$ для зберігання проміжних результатів:

• $dp[i]$ буде зберігати значення $f(i)$

int dp[100001];

Реалізуємо функцію $f(n)$, яка повертає кількість шуканих послідовностей з $0$ та $1$ довжини $n$. Використовуємо техніку мемоізації.

int f(int n)
{
  if (n == 1) return 2;
  if (n == 2) return 4;
  if (n == 3) return 7;
  if (dp[n] != -1) return dp[n];
  return dp[n] = (f(n-1) + f(n-2) + f(n-3)) % 12345;
}

Основна частина програми. Зчитуємо вхідне значення $n$.

scanf("%d",&n);

Ініціалізуємо масив $dp$.

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

Обчислюємо та виводимо значення $f(n)$.

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

Java реалізація

import java.util.*;

public class Main
{
  public static int MAX = 100010;
  static int f[] = new int[MAX];

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    f[1] = 2; f[2] = 4; f[3] = 7;
    for(int i = 4; i <= n; i++)
      f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
    System.out.println(f[n]);
    con.close();
  }
}

Python реалізація

Зчитуємо вхідне значення $n$.

n = int(input())

Ініціалізуємо список $dp$. У відповідні комірки заносимо значення f(1), f(2) та $f(3)$.

dp = [0] * (n + 4)
dp[1], dp[2], dp[3] = 2, 4, 7

Обчислюємо значення $f(i)$ за рекурентною формулою. Усі обчислення виконуємо за модулем $12345$.

for i in range(4, n + 1):
  dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 12345;

Виводимо відповідь.

print(dp[n])

Python реалізація – рекурсія з запам'ятовуванням

Збільшимо стек для рекурсії.

import sys
sys.setrecursionlimit(10000)

Реалізуємо функцію $f(n)$, яка повертає кількість шуканих послідовностей з $0$ та $1$ довжини $n$. Використовуємо техніку мемоізації.

def f(n):
  if n == 1: return 2
  if n == 2: return 4
  if n == 3: return 7
  if dp[n] != -1: return dp[n]

  dp[n] = (f(n - 1) + f(n - 2) + f(n - 3)) % 12345
  return dp[n]

Основна частина програми. Зчитуємо вхідне значення $n$.

n = int(input())

Ініціалізуємо список $dp$.

dp = [-1] * 100001

Обчислюємо та виводимо значення $f(n)$.

print(f(n))