Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

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

Вхідні дані

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

Вихідні дані

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

Тести

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

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

for(int i = 5; i <= n; i++) {

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

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

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

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

Посилання

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

Related Images:

Похожее

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

Мазурок Игорь Евгеньевич says: 10/05/2020 at 21:31

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

Войдите, чтобы ответить
- Анна Цивинская says: 24/06/2020 at 18:04
  
  Исправила инициализацию первых элементов массива, но, к сожалению, так и не придумала способ обойти время Вашего решения.
Мазурок Игорь Евгеньевич says: 24/06/2020 at 19:15

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

Войдите, чтобы ответить