[Условия задач] [Список тренировок]
7A. Упорядоченные дроби
[ordfrac] Лобовая реализация
Т.к. число N не превышает 255, то общее количество дробей будет невелико, поэтому можно получить все дроби двойным циклом, отбрасывая “повторки”.
[ordfrac] Ряд Фарея
Ряд Фарея предоставляет механизм генерации нужного ряда дробей сразу в отсортированном виде
7B. Сообщение
[message]
ДП + длинная арифметика. Подобная задача и некоторые ее вариации часто встречаются на школьных контестах.
7C. Игра умножения
[multgame] ДП с использованием map
Очередная задача на антагонистические игры. Чуть более сложней чем предыдущая 6С. Данная реализация более лаконичная, но требует логарифмического времени для получения ответа к решенной подзадаче.
[multgame] ДП + бинарный поиск
Разница от предыдущей реализации в том, что все возможные шаги в игре находятся в одном массиве. Тем самым задача по своей сути сводится к задаче 6С. Но тем не менее получение ответа на решенную подзадачу также выполняется за логарифмическое время, т.к. при этом приходится использовать бинарный поиск.
7D. Прямая и квадраты
[sqline] O(N*N)
Квадратичная реализация, наиболее уместная для предложенных ограничений. Используем факт, что прямая не пересекает многоугольник тогда и только тогда, когда он полностью находится либо в правой, либо в левой полуплоскости от прямой.
[sqline] O(N)
Линейная реализация, которая требует внимательности и аккуратности. Необходимо учесть 3 случая: горизонтальная, убывающая и возрастающая прямая. Будем двигаться по прямой небольшими шагами, равными стороне маленького квадрата, вдоль оси X. При этом будем анализировать значения Y. Рассмотрим 3 основных случая для возрастающей прямой:
 | Прямая пересекает только один квадрат |
 | Прямая пересекает два квадрата |
 | Прямая пересекает 4 квадрата |
Остальные случае предлагается рассмотреть самостоятельно.
7E. Lines(2)
[lines2]
Решение, аналогичное задаче 6E.Lines
7F. Удаление клеток
[remsquar]
Несложная задача. В качестве основных алгоритмов, решающих эту задачу на ум приходят DFS и BFS. Оба имею квадратичную сложность, но DFS писать проще. Торопится не стоит. Размерности матрицы таковы, что придется делать 250*250 рекурсивных вызовов. Поэтому вовремя одумываемся и быстро пишем BFS.
[Все решения]
Как видно дано 4 прямоугольника. Каждый из них дает по 2 проекции на оси X и Y. Избавляемся от дубликатов проекций. После чего получаем сетку, образованную этими проекциями. Эта сетка разбила первоначально пустой прямоугольник на N маленьких прямоугольников. В нашем случае N = 28. Чтобы найти суммарную площадь нужно перебрать каждый прямоугольник сетки и проверить, не является ли он вложенным хотя бы в один из первоначальных прямоугольников. 