Привет. Сегодня я буду разбирать задачки, которые помогут вам прокачать свои навыки при решении задач под буквой A. Задачи мы будем разбирать с acmp, так как на этом сайте находятся базовые задачи. Если интересно посмотреть, как дела с рейтингом у меня обстоят сейчас, то перейдите по ЭТОЙ ссылке.
На данный момент моя статистика такая:
---Давайте начнем с простого. Разберем сначала задачу Лифт. Задача на преобразования строк часто встречается в задачах A. Решение
Давайте разбираться. Предположим, что мы сейчас на нулевом этаже. Создадим три переменные: минимальный этаж, максимальный этаж, текущий этаж. Если мы поднялись на один этаж, то будем увеличивать текущую позицию и если она больше, чем максимальная, то будем увеличивать максимальную, а если текущая позиция меньше минимальной, то уменьшаем минимальную. Ответ мы получаем из суммы модулей максимального и минимального этажа и добавляем один этаж, так как если мальчик смог войти в лифт, то дом как минимум состоит из 1-го этажа.
Вот например для теста 21212 рисунок будет выглядеть так:
---Следующая задача будет на дп. Садовник-художник. Эта довольно жизненная задача (особенно для дачников). Решение
Очень просто догадаться о решении, если расписать N для 0, 1, 2, 3:
если у нас 0 деревьев, то количество способов = 0
если у нас 1 деревьев, то количество способов = 3
если у нас 2 деревьев, то количество способов = 6
если у нас 3 деревьев, то количество способов = 12
из этого вытекает рекурсивная формула, что dp[i] = dp[i - 1] * 2;
---Последняя задача будет про деда мороза. Подарки Деда Мороза.
Варианты решения:
1. написать алгоритм тупым перебором перебрать за O(x * y * z).
2. немного подумать и написать алгоритм за O( w / x * w / y)
Допустим мы подобрали X и Y грамм конфет, тогда Z можно вычислить следующим образом:
z = (w - x * i - y * j), где i и j - количество конфет X и количество конфет Y соответственно.
Удачи в повышении рейтинга
