Привет. Сегодня я буду разбирать задачки, которые помогут вам прокачать свои навыки при решении задач под буквой A. Задачи мы будем разбирать с acmp, так как на этом сайте находятся базовые задачи. Если интересно посмотреть, как дела с рейтингом у меня обстоят сейчас, то перейдите по ЭТОЙ ссылке.

На данный момент моя статистика такая:

---Давайте начнем с простого. Разберем сначала задачу Лифт. Задача на преобразования строк часто встречается в задачах A. Решение

Давайте разбираться. Предположим, что мы сейчас на нулевом этаже. Создадим три переменные: минимальный этаж, максимальный этаж, текущий этаж. Если мы поднялись на один этаж, то будем увеличивать текущую позицию и если она больше, чем максимальная, то будем увеличивать максимальную, а если текущая позиция меньше минимальной, то уменьшаем минимальную. Ответ мы получаем из суммы модулей максимального и минимального этажа и добавляем один этаж, так как если мальчик смог войти в лифт, то дом как минимум состоит из 1-го этажа.

Вот например для теста 21212 рисунок будет выглядеть так:

---Следующая задача будет на дп. Садовник-художник. Эта довольно жизненная задача (особенно для дачников). Решение. Очень просто догадаться о решении, если расписать N для 0, 1, 2, 3:

если у нас 0 деревьев, то количество способов = 0

если у нас 1 деревьев, то количество способов = 3

если у нас 2 деревьев, то количество способов = 6

если у нас 3 деревьев, то количество способов = 12

---Последняя задача будет про деда мороза. Подарки Деда Мороза. Решение.

Варианты решения:

1. написать алгоритм тупым перебором перебрать за O(x * y * z) // или за O(w/x * w/y * w/z), но это все равно будет долго.

2. немного подумать и написать алгоритм за O( w / x * w / y)

Допустим мы подобрали X и Y грамм конфет, тогда Z можно вычислить следующим образом:

z = (w — x * i — y * j), где i и j — количество конфет X и количество конфет Y соответственно!