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

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

5A. Дружественные числа 
[friendly] Precalc
Лобовое решение не проходит по времени. Поэтому воспользуемся “грязным приемчиком”, и подсчитаем все что нам нужно заранее и запишем все ответы в исходник.
5B. Скобки(2)
[brackets2]
Крайне полезная задача на понимание работы рекурсии. Рекурсивно получаем следующую скобочную последовательность. На каждом шаге храним количество открытых скобок и позицию, куда нужно ставить очередную скобку. Для получения корректных скобочных последовательностей нужно хранить стек, со всеми незакрытыми скобками.

5C. Маршрут(2)
[route2] Вариация с очередью
Несложное, но тем не менее необычное ДП. Решение отличается от авторского. Т.к. на каждом шаге будет достижима ~половина всех клеток поля, то решение автора будет более предпочтительным, чем приведенное. Но если процент достижимых клеток был бы меньше, то реализация с очередью могла оказаться более предпочтительной.
5D. Выпуклая оболочка
По этой задаче есть отдельный пост
[conhull] Алгоритм Джарвиса. Неоптимизированный
[conhull] Алгоритм Джарвиса. Оптимизированный
5E. Системы счисления
[scale] Венец всем операциям на ДА
Крайне полезная задача на закрепление основных операций на длинную арифметику.
До сегоднешнего дня (19Nov10) я переводил из i-ричной в 10-ую систему счисления двигаясь по числу с конца. Оказывается, если двигаться с начала, то можно сложение длинного с длинным заменить на сложение длинного с коротким. Также интересным моментом является определение количества разрядов в результирующем числе (константа max_size).
5F. День рождения
[birthday]
Дань традициям. Задача на даты. Полезна для начинающих. Требует внимательности, собранности и аккуратности.


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