e-olimp 8536. Заповнення смуги $3 \times n$

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані Вихідні дані
1 1
5 4
12 60
50 122106097

Код № 1

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

One thought on “e-olimp 8536. Заповнення смуги $3 \times n$

  1. Поздравляю! Вы заняли первое место по скорости работы программы. Теперь Вы возглавляете таблицу статистики этой задачи. Молодец!
    Но есть замечание. Вы инициализируете первый элемент массива при его описании, а несколько следующих — обычными присваиваниями. Почему не сразу так int F[51] = {0, 1, 1, 2, 3};
    Я решил написать более быстрое решение, чем ваше. И у меня получилось в 5 раз быстрее. Угадайте, как?

Добавить комментарий