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

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

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

    • Исправила инициализацию первых элементов массива, но, к сожалению, так и не придумала способ обойти время Вашего решения.

  2. Здесь довольно примитивная хитрость, которая называется «precalculation». Если трудоемкая функция задается на не очень большом множестве допустимых значений (например, 50), то можно задать ее таблично. Все значения вычислить заранее и записать в массив. На сленге это называют «захардкодить».

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