Задача B. Футболки от спонсора.

Пронумеруем размеры футболок целыми числами от 0 до 4. Для каждого размера будем хранить количество оставшихся футболок этого размера. При обработке очередного участника мы сначала определяем номер его размера, затем одним циклом перебираем размеры футболок и из тех размеров, футболки которых еще остались, выбираем самый подходящий (т.е. с ближайшим номером).

Задача D. Парковка.

Будем хранить множество машин, которое в данный момент находится на парковке. То, как мы его будем хранить, в данной задаче не принципиально. Для каждой машины, которая в данный момент находится на парковке, будем хранить ее длину и занимаемую ей позицию. При обработке запроса типа 2 нам надо найти машину, которая должна покинуть парковку, и удалить ее из множества. Для этого мы должны нумеровать машины и по номеру запроса понимать, к какой машине он относился. Теперь рассмотрим запрос типа 1. Поскольку водитель стремится поставить машину как можно ближе к началу парковки, то мы можем сузить множество рассматриваемых вариантов положений для парковки: включим в это множество начало парковки а также все позиции, которые находятся ровно через b метров после переднего края какой-либо машины. Для каждой из этих позиций мы должны выяснить, можно ли припарковать машину в ней, а затем выбрать самую ближайшую из допустимых позиций.

Задача E. Расческа.

Пусть входная матрица называется a. Посчитаем частичные суммы в каждой строке: . Естественно, все частичные суммы надо посчитать за O(nm). Теперь будем решать задачу динамическим программированием. Пусть d_i, j это наибольшая сумма чисел, которую мы можем взять в первых i строках, не нарушая в них условия "расчески", при этом взяв в i-й строке j чисел. Очевидна инициализация динамики: d_1, j = s_1, j. Теперь определим переходы для i > 1:

1) Если i четно, то .

2) Если i нечетно, то .

Вычисление значений d_i, j непосредственно по этим формулам имеет асимптотику O(nm²). Теперь заметим, что если в случае, когда i четно, перебирать j по убыванию, а если нечетно, то по возрастанию, и вычислять d_i, j в таком порядке, то максимум значений d_{i - 1, k} в предыдущей строке можно не вычислять каждый раз, а считать по ходу. Такое решение будет иметь сложность O(nm) и будет проходить все тесты.