Тренировка #3 [Меньшиков]

[Условия задач]                   [Список тренировок]

3A.Разложение на простые множители
[pfactor] Типовая соптимизированная реализация
Оптимизация заключается в пересчете верхней границы цикла(корень квадратный из N) при переходе к новому делителю.
3B.Перестановки(2)
[permut2] Рекурсивная реализация с подсчетом элементов
Реализация основана на разборе этой задачи из книги Меньшикова. Первоначально подсчитываем количество вхождений символов из первоначальной перестановки. Затем на i-ое место текущей перестановки ставим ближайший в лексикографическом порядке символ, счетчик которого имеет ненулевое значение, и декрементируем счетчик на единицу.
[permut2] Идентично [permut] next_permutation
Важный факт того, что генерация алгоритмом next_permutation не зависит от того есть ли дублирующие символы во входном наборе или нет. Общий вывод: любая корректная реализация задачи 3B пройдет на задаче 2B.
3C.Копилка
[piggy] ДП – Рюкзак
Классическая задача на ДП. Наверное самая классическая.
Рассмотрим самое сердце реализации:

1. if (i - W[j]>=0 && MIN[i-W[j]]!=INT_MAX)
2. {
3.   MIN[i] = min(MIN[i],MIN[i-W[j]] + P[j]);
4.   MAX[i] = max(MAX[i],MAX[i-W[j]] + P[j]);
5. }

где i – это текущий вес копилки, который пытаемся набрать,
W[j] – вес рассматриваемой j-ой монеты,
P[j] – цена рассматриваемой j-ой монеты.
Итак второе условие в if’e сигнализирует о том, что вес i-W[j] уже был набран каким-то набором из предыдущих монет. На текущем шаге пытаемся набрать текущий вес i. При поиске минимальной стоимости текущего веса мы можем уменьшить текущее значение, если оно больше значения MIN[i-W[j]] + P[j], а именно минимальной стоимости суммарного веса i-W[j] и стоимости текущей монеты. Случай с максимальной стоимостью решается похожим способом.
3D.Открытка и конверт
[postcard] Школьная геометрия
Признаюсь в свое время сам задачу ниасилил. Для понимания и по уровню реализации самым удачным решением считаю “Вариант 2”(стр. 130) оригинального издания.
3E.Длинное произведение
[longprod]
Менее распространенная операция на ДА, чем длинный плюс, но имеет очень важное значение в задачах на комбинаторику. Введена оптимизация (строка 47) – внутренний цикл работает только при наличии разряда для переноса. Сама оптимизация позаимствована с сайта e-maxx
3F.Змейка
[serpent] 1 вариант (оптимизированный)
Когда открыл исходник спустя 2.5 месяца ужаснулся от увиденного. Сложно для понимания сходу. Плюсом является то, в ходе решения все рассматриваемые точки находятся строго внутри матрицы. Т.к. на задачу маленькие ограничения лучше взять за основу более читабельную вторую реализацию.
[serpent] 2 вариант (жизненная реализация)
Данный исходник был написан на последней субботней тренировке 15May2010. Не содержит ничего лишнего. ПрофПригоден для использования.


[Все решения]