at1's blog

By at1, 15 years ago, In Russian

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))).
  • Vote: I like it
  • +3
  • Vote: I do not like it