Обсуждение контеста

Задача А. Треугольники

Тематика: Теорема Пифагора, перебор

В данной задаче нужно было написать функцию, проверяющую, что три точки образуют прямоугольный треугольник. Сделать это можно было множеством способов, один из самых простых - теорема Пифагора

Чтобы избежать проблем с погрешностью, можно было не извлекать корень, а использовать квадрат расстояния.

Чтобы проверить треугольник на почти прямоугольность, нужно было поочередно подвигать каждую точку во все 4 направления и проверить получившийся треугольник в нашей функции. Для быстрого перебора смещения, можно использовать два массива dx={-1,0,1,0} и dy={0,1,0,-1}. Тогда следующий код давал бы нам координаты смещенной точки:

for (int i = 0; i < 4; i ++)

{

int x = dx[i] + px;

int y = dy[i] + py;

}

Задача B. Платформы

Тематика: Симуляция

Рисунок к задаче:

В данной задачи нужно было определить координату падения кузнечика. Для этого просто будем хранить положение кузнечика в данный момент.

Для того, чтобы программа не работала слишком долго, нужно "продвигать кузнечика" по платформе за О(1) (не в цикле). Кузнечик сделает j = (right_i-x)/d прыжков по i-ой, платформе, где x - координата кузнечика (он уже стоит на платформе) а right_i - правая координата платформы. Поэтому кузнечка сразу можно передвинуть на j*d право.

Задача C. Полоска

Тематика: Перебор

Для решения данной задачи нужно было хранить две суммы S₁ - сумма чисел слева от разреза (изначально равна 0) и S₂ - сумма чисел справа от разреза (изначально равна сумме всех чисел на полоске). В цикле двигаем место разреза слева направо, изменяя значения сумм, и, при необходимости, увеличиваем ответ

Задача D. Продавец Вася

Тематика: Жадный алгоритм, длинная арифметика

В задаче D потребуется длинная арифметика (сложение), так как число 2²⁰⁰⁰ не вместится в int64.

Нам дано условие того, что продавец для каждого размера флешки встретится не более одного раза. Так как 2^x > 2^x-1 + 2^x-2 + ... 2⁰, то прибыль от флешки с самым большим объемом будет больше чем если бы мы продали все остальные флешки. Поэтому в первую очередь нужно попытаться продать самую большую флешку, потом флешку поменьше и т.д. Таким образом, нужно пытаться продать флешки по убыванию их стоимости

Задача E. Флаг 2

Тематика: Динамическое программирование

В задаче про флаг необходимо воспользоваться методом динамического программирования. Мы будем считать функцию DP(level, A, B) (где A и B - номера цветов, от 0 до 25), которая возвращает минимальное число перекрасок, нужное чтобы перекрасить первые level полосок, причем последняя полоска будет иметь вид ABABAB...

Для пересчета данной функции сначала посчитаем, сколько перекрасок нужно, чтобы привести полоску с номером level к виду ABABAB... (пусть это будет число D). Заметим, что полоску можно покрасить таким образом, если первый цвет предыдущей полоски не был "A", а второй цвет не был "B" (условие того, что смежные клетки не должны быть одного цвета) или же это должна быть первая полоска. Поэтому DP(level, A, B) = min(DP(level-1, i, j)) + D , i = 0..25, j = 0..25, i != j, i != B, j != A.

Оценим время работы программы: O(N*26*26*(M+26*26)), эта константа не превышает 4*10⁸

Спасибо за внимание! Решения не претендуют на оптимальность