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

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

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.


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