Презентации по Математике

Командная олимпиада “Высшая проба” 2019. Разбор задач
Командная олимпиада “Высшая проба” 2019. Разбор задач
Задача A. Покраска деревьев Тема: Пересечение отрезков Нужно понять, пересекаются ли отрезки или нет. Проще всего упорядочить отрезки (например, по заданному нам центру) и проверить, что правая граница левого отрезка больше либо равна левой границе правого. Тогда есть пересечение и ответ: большая из правых границ минус меньшая из левых границ отрезков. На рисунке красный - это “левый” отрезок, а синий - правый В противном случае отрезки не пересекаются и нужно просто сложить их длины. Задача B. Продавец рыбы Тема: Линейный поиск Переберём каждый из N дней в качестве дня, в который мы покупаем рыбу. Определим максимальную прибыль, которую можно получить при покупке в этот день. Для этого среди следующих K чисел найдём максимальное и посчитаем разность. Среди всех таких разностей найдём максимальную - она и будет ответом. Сложность решения: O(NK) ~ 1 000 000 000 операций
Продолжить чтение