A. Треугольник
Из трех палочек с длинами a, b, c > 0 можно составить треугольник ненулевой площади тогда и только тогда, когда:|a - b| < c < a + b (+)
При вырожденном случае в (+) одно из неравенств обращается в равенство. (Для обоснования можно построить окружности радиуса a и b с центрами в концах отрезка длины c, и проверить когда они пересекаются).
Таким образом, можно перебрать все тройки чисел из данных 4-х и проверить (+).
B. Кабинет президента
Достаточно перебрать все клетки, соседние с клетками цвета стола президента, помечая их цвета. То есть после процедуры мы будем знать для каждого цвета, является ли он соседним с данным нам. Ответ на задачу - количество помеченных цветов.C. Алиса, Боб и шоколад
Необходимо промоделировать описанную в условии игру. Имеем два указателя на начало и конец массива длин шоколадок, каждый раз смещаясь по первому, второму или обоим (в зависимости от длин шоколадок). Сместившись только по одному указателю, нужно уменьшить длину недоеденной шоколадки.Единственная техническая трудность - правильно обработать последнюю шоколадку, можно ошибиться или зациклиться, если участники перейдут к ней одновременно.
E. Экспозиция
Рассмотрим функцию f(l, r) = max(hi) - min(hj), l ≤ i, j ≤ r. (<максимум на отрезке> - <минимум на отрезке>). Эта функция как раз и отражает разницу между самой высокой и самой низкой книгами на взятом отрезке.Если l возрастает при фиксированом r, то функция убывает, аналогично, по r функция растет. К монотонной по r функции f(l0, r) можно применить бинарный поиск и найти наибольшее r, для которого f(l0, r) ≤ k. Подходящая структура данных для поиска минимума (максимума) на отрезке - дерево отрезков.
Для каждого левого конца можно найти максимально удаленный правый за время O(n*log2(n)). (n - левых концов, O(log(n)) вычислений f с помощью дерева отрезков за O(log(n))). Из этого множества отрезков ответом являются те, длина которых максимальна.
Можно упростить это решение и по написанию кода и по времени "техникой двух указателей". pl указывает на начало отрезка, pr на конец, причем если f(pl, pr) < k, то увеличиваем pl, иначе pr. Из-за уже указанных свойствах монотонности f по l и r, можно утверждать, что [pl, pr] заметут все искомые отрезки.
Теперь можно увидеть, что мы используем всего три операции:
<добавить элемент pr>
<удалить элемент pl>
<взять максимум - минимум на текущем отрезке>
То есть можно просто кидать/удалять элементы вида (hi, i) в set (структура данных организующая множество, построенная на любом сбалансированном дереве, как правило есть стандартных библиотеках языка). Минимум - левый элемент в дереве, максимум - правый.
Сложность алгоритма с сетом O(n*log(n)). (≤ 2n смещений pl, pr, на каждом шаге обращение к сету за O(log(n))).