e-olymp-8577. Супер платформи

Условие

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається $\left|y_2–y_1\right|$енергії, де $y_2$ та $y_1$ – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається $3·|y_2–y_1|$ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від $k_{min}$ до $k_{max}$ разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому $k_{min}$ та $k_{max}$. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ $n (1 \leq n ≤ 10000)$. Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа $k_{min}$ та $k_{max}$ $\left(0 ≤ k_{min} ≤ k_{max} ≤ \frac{n–1}{2}\right)$.

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Тесты

Ввод Вывод
1 3
1 5 10
0 1
9
2 9
1 3 2 3 8 10 25 17 25
2 4
24

Код

Решение

В решении суперприёмы из условия для удобства буду называть суперпрыжками.
Решим эту задачу динамически. На каждом шаге будем искать масив, где записано сколько минимально надо потратить энергии что б добраться до каждой платформы, сделав ровно $j$ суперпрыжков. Легко получить рекурсивную зависимость: для того, что бы попасть на $i$ платформу нам надо либо прыгнуть с предыдущей $(a_{j (i-1)}+|p_i-p_{i-1}|)$ либо сделать суперпрыжок с платформы под номером $i-2$ $( a_{(j — 1)(i — 2)} + 3|p_{i — 2} — p_i| )$. Не забудем про то, что не всегда можно прыгнуть с предыдущей так как мы могли бы и не попасть на нее за $j$ суперпрыжков. Таким образом для некоторых платформ( а именно первых в каждом масиве) мы будем делать суперпрыжок с платформы под номером $i-2$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.

Оптимизация

поскольку для генерации нового масива используется только предыдущий можно не хранить всю матрицу. Это позволит нам не засорять память.

Ссылки

e-olymp 908. Те, что делятся на 6

Задача: Те, что делятся на 6

Для [latex]N[/latex] целых чисел определить сумму и количество положительных чисел, которые делятся на 6 без остатка.

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

В первой строке задано количество чисел [latex]N[/latex]$\left(1 \leq N \leq 100\right)$, в следующей строке через пробел заданы сами числа, значения которых по модулю не превышают $10000$.

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

В единственной строке выведите сначала количество указанных чисел и через пробел их сумму.

Тесты

Ввод Вывод

3

12 15 18

2 30
4

-10 -15 42 -24

1 42
2

6 0

1 6
3

-6 -12 -32

0 0

Решение

Заводим 2 переменные: сумму и количество. Каждый раз, когда мы читаем число, проверяем положительно ли оно и делится ли на 6 (Обычно желательно сначала проверять наимение вероятное условие, т.к. программа реже будет лишний раз проверять второе условие и, как следствие, сделает меньше действий, но в этой задачи это особой роли не играет из-за малого ввода), если оба условия выполняются, добавляем к счетчику 1, а к сумме введенное число. По окончанию ввода выводим сумму и количество через пробел.

Ссылки

e-olymp 8380. Эскалатор

Задача: Эскалатор

В Баку вскоре откроется новая станция метро. Эскалатор в метро состоит из n ступенек, пронумерованных целыми числами от $1$ до $n$. На ступеньках с номерами, кратными десяти, а также на первой и последней ступеньке, пишут их номера. При записи номера на каждую записанную цифру уходит одно и то же количество краски.

Чтобы рассчитать необходимое количество краски, требуется узнать, сколько цифр будет написано. Напишите программу, которая определяет, сколько всего цифр будет использовано в номерах подписанных ступенек.

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

Одно целое число $n\;\left(1 \leq n \leq 10^{18}\right)$ — количество ступеней эскалатора.

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

Выведите суммарное количество цифр в номерах подписанных ступенек.

Тесты

Ввод Вывод
1000000000000000000 1788888888888888908
242 67
250 67
999 292
1000 293
1 1
2 2

Решение

Идея решения заключается в том чтобы искать количество помеченных ступенек на  отрезках $10-99,100-999,\ldots,10^{x}-\left(10^{x+1}-1\right).$ Легко понять что помеченных ступенек $9\cdot 10^{x}.$ Это суть метода, а остальное это реализация, которую я покажу в программе.

Ссылки

e-olymp 945. Без средней

Задача: Без средней

Записать заданное трехзначное натуральное число без средней цифры.
Входные данные
Одно натуральное трехзначное число.
Выходные данные
Вывести трехзначное число без средней цифры.

Тесты

Ввод Вывод
157 17
242 22
578 58

Решение

Есть как минимум два способа решения данной задачи. Первый очень простой — нам просто нужно вывести 1-ю цифру и 3-ю. Таким образом мы выведем число без средней.

Второй способ сложнее и выполняется дольше, но он использует линейные вычисления. Мы вводим а, затем получаем разряд сотен умножаем его на 10, потом единиц и суммируем. Таким образом мы получим число, у которого разряд единиц от предыдущего а десятки от сотен предыдущего. Таким образом мы исключаем среднее.

Ссылки