581A — ???
The first number in answer (number of days which Vasya can dress fashionably) is min(a, b) because every from this day he will dress one red sock and one blue sock.
After this Vasya will have either only red socks or only blue socks or socks do not remain at all. Because of that the second number in answer is max((a - min(a, b)) / 2, (b - min(a, b)) / 2).
Asymptotic behavior of this solution — O(1).
581B — ???
This problem can be solved in the following way. Let's iterate on given array from the right to the left and will store in variable maxH the maximal height if house which we have already considered.Then the answer to house number i is number max(0, maxH + 1 - hi), where hi number of floors in house number i.
Asymptotic behavior of this solution — O(n), where n — number of houses.
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 количество заданных навыков героя.
