260A - Добавление цифр

Сначала попробуем приписать справа любую цифру от 0 до 9, которая подойдет под условие задачи. Если это не получится, сразу выведем -1. В противном случае остальные n–1 можно сделать 0, так как делимость от этого не пропадет.

260B - Древнее пророчество

В этой задаче нужно было перебрать все даты от 2013 до 2015 года (високосных годов среди них нет), посчитать количество вхождений каждой даты в исходную строку и найти максимум. В году 365 дней, следовательно это решение за (3·365·N).

260C - Коробки и шарики

Сначала опишем простой способ получения решения. Будем по одному шарику доставать из коробок, начиная с коробки x справа налево (действие назад). В какой-то момент в текущей коробке окажется 0 шариков. Это коробка является начальной для нашей исходной задачи, то есть та, откуда мы взяли все шарики и начали раскладывать. Тогда в эту коробку положим число шариков, равное количеству шариков, которое мы только что достали из всех коробок.

Только так задачу решать нельзя, потому что это количество может быть очень большим. Заметим, что прежде чем столкнуться с этой ситуацией, мы несколько раз пройдем по всему массиву и вычтем 1. Поэтому этот процесс можно ускорить, предварительно убрав из каждой коробки, например, minv - 1 шарик, где minv — минимум в исходном массиве. После этого останется выполнить O(N) указанных выше простых операций.

260D - Черно-белое дерево

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

На каждом шагу будем выбирать вершину v с наименьшей суммой из белых и черных. После этого найдем любую вершину u противоположного цвета и проведем ребра (u, v) веса s[v], а из суммы вершины u вычтем сумму вершины v, то есть s[u] = s[u]–s[v]. Будем продолжать этот процесс, пока не он не закончится. Циклов в графе не получится, потому что каждый раз, обнуляя очередную вершину, будем ее удалять. В какой-то момент может оказаться, что мы удаляем последнюю вершину одного из цветов. Поскольку мы поддерживаем инвариант равенства сумм черных и белых, оставшиеся вершины нужно просто присоединить к графу любым корректным образом с весом ребра 0.

260E - Разделение королевства

Переберем 9! способов расположений чисел a[i] по 9 областям. Зафиксировав некоторое положение, то есть некоторую решетку, легко посчитать количество городов левее левой вертикальной прямой, правее правой вертикальной прямой, ниже нижней горизонтальной прямой и выше верхней горизонтальной прямой. Каждое из этих значений есть сумме некоторых трех значений a[i].

Будем считать, что прямые из ответа всегда проходят по полуцелым координатам. Тогда, зная указанные выше 4 числа, можно однозначно определить отдельно по x и y, как должны расположиться все 4 прямые. Остается лишь только проверить, что во всех областях нужное количество точек.

Для каждой из четырех зон (левее левой вертикальной прямой, правее правой вертикальной прямой, ниже нижней горизонтальной прямой и выше верхней горизонтальной прямой) отдельно проверим, что все три области этой зоны содержат нужное число точек. Это будет делать при помощи сканирующей прямой и дерева отрезков, которое умеет искать сумму на отрезке и делать обновление в точке. Для этого сложим все эти запросы в некоторый массив, отсортируем и будем обрабатывать слева направо. Заметим, что проверив 8 условий из 9 для каждого из 9! расположения решетки, центральную область проверять не нужно, она восстановиться сама собой. Если ни одно положение не подойдет, нужно вывести -1.