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

e-olymp 798. Платформы

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

Входные данные

Первая строка содержит количество платформ $n  (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

Выходные данные

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

Ввод Вывод
1 4
1 2 3 30
29
4
1 2 3 4
2 2
7 23
16
2
1 2
3 5
0 1 0 1 0
0
3
1 3 5

Код

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

  1. Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
  2. Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки