A(1). Посортируем банки по x. Если расстоние между первым и последним меньше d, то надо вывести -1 -1. Иначе решение есть и его можно найти за линейное время методом двух указателей. Посчитаем массив максимумов W_i = max(w_i,..,w_n). Начнем идти двумя указателями от начала, первый указатель перебирает банк i с меньшей x-координатой, второй указатель поддерживаем на банк j с минимальной x-координатой, большей, чем x[i] хотя бы на d. В качестве пары к банку i можно взять любой банк среди j,...,n. Максимум среди них уже посчитан. Сложность решение O(n*log(n))
B(1). Разделим все отрезки на x-отрезки (параллельные Oy, среди четырех чисел задающих отрезок две x координаты совпадают) и y-отрезки (параллельные Ox). Для каждого x-отрезка найдем множество y-отрезков, с которыми оно пересекается. Для каждой пары x-отрезков найдем пересечение множеств y-отрезков, с которыми они пересекаются. Если в этом множестве k элементов, то прямоугольников на этой паре x-отрезков можно построить k*(k-1)/2. Итоговая сложность решения O(n^3). Если пересекать множества с помощью битсетов, то n^3/32
C(1). Пусть высота башни k, тогда независимо от расположения кубиков сумма на боковой поверхности равна 14*k. Если k=1, то суммарная поверхность равна 21 (это отдельный случай). Иначе мы можем выбрать любые числа в качестве верхнего и нижнего и получить любое n, которое имеет остаток при делении на 14 равный от 2 до 12 и которое >= 14*2.
D(3). Сразу удалим подряд идущие xX (если появятся новые, то их тоже удалим) прибавив их к ответу, если в ходе этого процесса появится что-то противоречивое xY или большая буква в начале или маленькая в конце, то выведем, что ответа нет. Оставшееся слово выглядит как конкатенация слов вида s*S (не более 5, тк звездочек не больше 5), где s-слово из маленьких букв, S - из больших, s и S могут быть пустыми. Далее считаем, какое минимальное количество символов надо добавить с помощью квадратичной динамики (d[i,j] для каждого подслова)
E(2). Заметим, что если какую-то фигуру съесть, то новых ограничений на передвижения белого короля не появится. Значит можно действовать жадно - есть пока это возможно. Для того чтобы минимизировать количество ходов нужно поддерживать текущее состояние - координаты белого короля и маску еще не съеденных черных фигур. Для каждой маски можно заранее посчитать, какие клетки доски не побиты. Тогда в каждом состоянии достаточно запустить поиск в ширину из текущей позиции короля по непобитым клеткам, который вычислит для каждой фигуры, которую можно съесть минимальное время за которое до нее можно дойти. Взяв потом минимум по возможным переходам получим ответ в этом состоянии динамики. Итоговая сложность такого алгоритма равна 2^k*n*m*n*m, это много. Но на самом деле для данной маски оставшихся фигур нужно вычислять значение динамики только для положений короля совпадающих с одной из уже съеденных черных фигур (а когда еще никого не съели, то только для начального положения короля). Тогда состояний становится не более k*2^k/2 (k - количество черных фигур), а сложность перехода n*m, что уже влезает в таймлимиты.
F(2). Пусть НОД всех возможных чисел равен d, тогда ответ - это все возможные делители d (которые ищутся перебором до sqrt(d), d < 10^{14}, тк все числа не больше 10^{14}). Остается найти d. Заметим, что на d делятся все разности чисел. Если цифр меньше 10, то среди разностей есть числа равные сумме степеней 10, соответствующие определенной букве. Но нод таких сумм очевидно делит любое исходное число, значит d ему равен(например если слово abcabca, то d=нод(1001001,0100100,0010010)). Остается случай когда разных цифр 10. Все возможные разности можно ограничить теми, которые получаются переменой значений двух букв между собой, все остальное будет их суммой (и будет делится на их нод автоматически). Таких разностей будет 10*9/2, d равно ноду их и любого числа из исходного множества (например если слово abcabca (забудем пока, что в нем не 10 цифр), то d=нод(1001001-0100100,1001001-0010010,0100100-0010010,1231231)), тк любое число можно получить прибавив к конкретному какую-то разность перестановок двух цифр (это следствие того, что любая перестановка является композицией транспозиций)
G(3). Заметим, что если решение оптимальное, то увеличить скорость нельзя, это значит, что на каком-то из светофоров в тот момент, когда мы по нему проезжаем только что загорелся зеленый свет, либо скорость максимально допустимая. Давайте найдем все возможные значения скорости, которые такому условию удовлетворяют. Переберем все светофоры, на каждом из них не более x_i/v_min/(g_i+r_i) моментов времени, когда красный переключается на зеленый и при этом это происходит в момент времени удовлетворяющий скоростным ограничениям. Значит разных скоростей надо будет перебрать не более 2000000. Однако время проверки каждой такой скорости будет слишком большим, поэтому будем проверять их все сразу - начнем двигать скорость от минимума к максимуму, и хранить количество светофоров, которые в данный момент проезжаем на красный. Когда скорость переходит очередную точку перемены цвета на каком-то из светофоров, то вычитаем или прибавляем к этому счетчику.
H(3). Вначале разделим станции из входных данных на области. Возьмем какую-нибудь вершину степени 4 и и будем идти из нее в глубину, пока не встретим еще вершин степени 4 (их будет две разных, каждая встретится по два раза). Все что обойдется таким образом будет принадлежать двум областям, на стыке которых эта вершина лежит. На эти две области станции можно разделить исходя из того, в какой станцию степени 4 пришла их ветка. После этого помечаем все, что уже обошли и больше сюда не ходим, берем следующую вершину степени 4 и тд. В итоге мы знаем какие у нас области и какая с какой имеет общий станцию. Станции принадлежащие одной области можно разделить между компаниями пополам, но если в ней нечетное число станций, то одна станция точно останется не купленной, но можно делать такой станцию, которая лежит на стыке областей, тогда нам удастся убрать нечетный цикл сразу из двух областей. Рассмотрим три случая: 1) нечетных областей нет вообще, тогда если граф двудольный, то разделим все станции между компаниями, если нет, то как минимум одну станцию придется выбросить. Выбросим любую станцию, которая лежит на стыке областей, утверждается, что после этого граф станет двудольным и все оставшееся можно разделить между компаниями. 2) все области нечетные. Если областей четное число, то выкинем "стыковые станции" через одну и граф распадется на деревья, каждое из них двудольное и его можно целиком разделить между компаниями. Если областей k нечетное число, то придется удалить (k+1)/2 "стыковую станцию". 3) Есть и четные области и нечетные. Посмотрим на граф областей, он представляет из себя цикл, в котором встречаются отрезки подряд идущих областей с нечетным числом вершин. Из каждого отрезка длины k состоящего из нечетных областей надо выкинуть (k+1)/2 вершин чередующихся "стыковых станций", после этого граф станет двудольным и оставшиеся станции можно будет разделить между компаниями.
I(4). В начале запустим поиски в ширину из каждого гения и найдем расстояния от них до всех других вершин. Вторая компания выиграет, если сможет в ответ на ход первой компании U взять какую-то вершину V, которая либо 1) находится ближе U к каким-то из двух гениев 2) находится на равном расстоянии с U от двух гениев и ближе к 3-му, чем U. Ясно, что второй случай первая компания может не допустить, ей достаточно не делать парето-неоптимальный первый ход. Для каждой пары гениев можно посмотреть какие пары расстояний до них дают все вершины и оставить только те вершины, для которых нету вершины с парой строго меньших расстояний. Эти три множества надо пересечь, если пересечение не пусто, то первая компания выиграла, иначе вторая.
J(3). Сразу домножим длины всех ребер на 2, чтобы радиус графа был целым. Найдем диаметр d в дереве и путь, который соединяет эти две вершины. Ясно, что хотя бы одно ребро на этом пути надо заменить. Найдем центр диаметра (он может быть как в вершине, так и внутри какого-то ребра, если так, то добавим на это ребро вершину, так что бы центр оказался в вершине). Найдем расстояния от центра до всех вершин графа. Все эти расстояния не больше d/2, а те вершины, которые находятся на расстоянии ровно d/2 могут быть краями диаметра. Нам нужно сделать так, чтобы на пути до каждой такой вершины, хотя бы одно ребро было заменено. Это можно вычислить динамикой в поиске в глубину.
K(1). Нужно для каждой открывающейся скобочки честно проверить то, что написано в условии за один проход до ближайшей скобочки (но не до конца строки, иначе будет тл).
L(3). Переведем задачу на язык перестановок. Будем считать тождественной перестановку чисел, в которой они отсортированы, нам надо превратить имеющуюся перестановку в тождественную. Ответ никогда не больше 2. Если массив уже упорядочен, то ответ 0. Разложим нашу перестановку в произведение простых циклов. Если все циклы длины 2, то можно все сделать за одну операцию. Если есть хоть один цикл длины 2, то очевидно одной операции будет мало. Любой простой цикл можно привести в тождественный за две операции, разобрав отдельно случай четного и нечетного цикла.