581A — Хипстер Вася
Первое ответное число (количество дней, которое Вася сможет быть одет по моде) это min(a, b), так как каждый из этих дней он будет надевать по одному красному и по одному синему носку.
После этого у него останутся либо только красные носки, либо только синие носки, либо не останется носков вовсе. Поэтому второе ответное число это max((a - min(a, b)) / 2, (b - min(a, b)) / 2).
Асимптотика решения — O(1).
581B — Элитные дома
Данная задача решается следующим образом. Пойдем по массиву справа налево и будем поддерживать в переменной maxH максимальную высоту дома, который мы уже рассмотрели. Тогда ответом для i-го дома будет число max(0, maxH + 1 - hi), где hi количество этажей в 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! * 2k * s), где s — суммарная площадь заданных прямоугольников.
Также данная задача для 3 прямоугольников имеет решение с разбором случаев с асимптотикой O(s), где s — суммарная площадь заданных прямоугольников.
581D — Развитие навыков
Данную задачу можно решать несколькими способами. Рассмотрим самый понятный способ, который укладывается в заданное время.
Отсортируем заданный массив следующим образом — из двух чисел левее должно стоять то, к которому нужно добавить меньше единиц улучшений, чтобы оно стало кратно 10. Например, если исходный массив {45, 30, 87, 26}, то после сортировки он должен выглядеть следующим образом — {87, 26, 45, 30}.
Теперь проитерируемся по отсортированному массиву слева направо по i от 1 до n. Пусть cur = 10 - (aimod10). Если cur ≤ k, присвоим ai = ai + cur, а из k вычтем cur, иначе, если cur > k выйдем из цикла.
Следующим шагом проитерируемся по массиву аналогичным образом.
Осталось посчитать ответ ans — проитерируемся по массиву по i от 1 до n и присвоим ans = ans + (ai / 10).
Асимптотика решения — O(n * log(n)), где n количество заданных навыков героя.
