Задача D. Магiчнi послiдовностi


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

Назвемо послiдовнiсть довжини \(N\) з двох чисел магiчною, якщо в нiй будь-яка пiдпослiдовнiсть з двох або бiльше однакових чисел має парну довжину.

Необхiдно порахувати кiлькiсть таких магiчних послiдовностей.

Обмеження:
  • \(1 \le N\), \(A\), \(B \le 32\)
Формат входових даних:

Три цiлих числа: \(N\), \(A\), \(B\).

Формат виходових даних:

Одне цiле число --- кiлькiсть таких послiдовностей.

Приклад входових даних:
3 1 2
Приклад виходових даних:
6
Пояснення:

\(N=3\), а числа, якi можна використовувати: \(1\) та \(2\). Перелiчимо всi можливi послiдовностi та перевiримо їх:

  • \([1, 1, 1]\) — Недопустимо (три одиницi поспiль).
  • \([1, 1, 2]\) — Допустимо (двi одиницi, одна двiйка).
  • \([1, 2, 1]\) — Допустимо (одиницi та двiйка поодинцi).
  • \([1, 2, 2]\) — Допустимо (одиниця, двi двiйки).
  • \([2, 1, 1]\) — Допустимо.
  • \([2, 1, 2]\) — Допустимо.
  • \([2, 2, 1]\) — Допустимо.
  • \([2, 2, 2]\) — Недопустимо.

Загальна кiлькiсть допустимих послiдовностей: \(6\).


Comments

There are no comments at the moment.