Ctrl K

Забор без трёх одинаковых подряд

Средняя
Забор состоит из posts столбов, стоящих в ряд, и есть colors разных красок. Каждый столб красят ровно одной краской, но три или больше соседних столба подряд не должны быть одного цвета. Сколькими способами можно покрасить забор?
Пример 1
posts=3, colors=2 → 6

Из 2³ = 8 раскрасок не подходят две — все три столба одного цвета.

Пример 2
posts=4, colors=1 → 0

С одной краской три соседних столба неизбежно совпадут.

Пример 3
posts=2, colors=5 → 25

Два столба можно красить как угодно: 5 · 5 = 25.

Ограничения
  • 1 ≤ posts ≤ 50
  • 1 ≤ colors ≤ 10⁵
  • Ответ не превышает 2³¹ − 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый длинный зеркальный кусок СредняяВсе правильные скобочные строки СредняяМеньше всего прыжков до конца СредняяСамая прибыльная серия дней СредняяДобраться до последней клетки Средняя
загружаем Python…
Вход
posts=3, colors=2
Ожидается
6

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 37 тестов на сервере, включая скрытые.