581A — Хипстер Вася

Первое ответное число (количество дней, которое Вася сможет быть одет по моде) это min(a, b), так как каждый из этих дней он будет надевать по одному красному и по одному синему носку.

После этого у него останутся либо только красные носки, либо только синие носки, либо не останется носков вовсе. Поэтому второе ответное число это max((a - min(a, b)) / 2, (b - min(a, b)) / 2).

Асимптотика решения — O(1).

581B — Элитные дома

Данная задача решается следующим образом. Пойдем по массиву справа налево и будем поддерживать в переменной maxH максимальную высоту дома, который мы уже рассмотрели. Тогда ответом для i-го дома будет число max(0, maxH + 1 - h_i), где h_i количество этажей в i-м доме.

Асимптотика решения — O(n), где n — количество домов.

581C — Три логотипа

Данная задача решается несколькими способами, рассмотрим один из них.

Для начала подсчитаем суммарную площадь s данных нам прямоугольников. Тогда сторона ответного квадрата это sqrt(s). Если sqrt(s) не целое число, выводим -1. Иначе сделаем следующее.

Переберем порядок, в котором будем добавлять заданные прямоугольники в квадрат (это можно сделать с помощью next_permutation(), а также для каждого порядка переберем будем ли мы переворачивать текущий прямоугольник на 90 градусов или нет (это можно сделать с помощью двоичных масок). Изначально на каждой итерации квадрат c[][], в который мы добавляем прямоугольники ничем не заполнен (пустой).

Для каждого из добавляемых прямоугольников сделаем следующее — найдем самую верхнюю левую свободную клетку free в квадрате c[][] (напомним, что мы также перебираем, поворачиваем ли мы прямоугольник на 90 градусов или нет). Попытаемся наложить текущий прямоугольник в квадрат c[][], причем его левый верхний угол должен совпадать с клеткой free. Если текущий прямоугольник полностью помещается в квадрат c[][] и не накладывается на уже занятую каким-то другим прямоугольником клетку, заполним соответствующие клетки в квадрате c[][] нужной буквой.

Если после добавления всех трех прямоугольников не нарушилось ни одно из условий и весь квадрат c[][] оказался заполненным мы нашли ответ — выводим квадрат c[][].

Если ответ не нашелся ни для одной перестановки прямоугольников — выводим -1.

Для произвольного количества прямоугольников k асимптотика решения — O(k! * 2^k * s), где s — суммарная площадь заданных прямоугольников.

Также данная задача имеет решение с разбором случаев с асимптотикой O(s), где s — суммарная площадь заданных прямоугольников.

581D — Развитие навыков

581E — ???

581F — ???