9. Решающий удар

Для определения вероятности посчитаем динамику
    v[n][d] — количество исходов при бросании n игральных костей,
              при которых сумма результатов равна d.

База динамики
Для первой кости и каждого из исходов 1 <= d_roll <= f
    v[1][d_roll] = 1.

Переход динамики
Уже бросили (n - 1) кость и сумма результатов равна d,
бросаем ещё одну кость и выбрасываем на ней d_roll, тогда
    v[n][d + d_roll] увеличивается на v[n - 1][d].
При добавлении очередной кости суммируем по всем d и d_roll.

Количество нужных нам исходов получаем суммой
    S = sum v[n][d], max(1, D - m) <= d <= n * f.

Итоговая вероятность равна
    S / f^n.

7. Планировщик

Пусть X[i] = P[i] + T[i].

В задаче нужно выбирать среди N значений X[i] минимальное — для этого отлично подойдёт бинарная куча.
Кроме того, нужно на каждой итерации прибавлять единичку ко всем X[i] (кроме одного).
Чтобы этого не делать, давайте договоримся, что будем хранить в программе Y[i] = X[i] — t, где t — сколько секунд прошло с начала работы планировщика.
В этом случае прибавление единички ко всем X[i] происходит автоматически благодаря тому, что мы увеличиваем t после каждой итерации.

Решение заключается в том, чтобы хранить и поддерживать Y[i] для всех процессов в бинарной куче.
На каждой итерации нужно выбрать процесс с минимальным значением Y[i], и присвоить ему Y[i] := P[i] — (t+1), обновив его положение в куче.
Чтобы среди процессов с равным приоритетом выбирался процесс с минимальным номером, можно хранить в куче на максимум пары (Y[i], -i) с лексикографическим сравнением.

Разумеется, свою бинарную кучу писать не обязательно.
В C++ для этого есть push_heap/pop_heap, priority_queue и set, а Java есть TreeSet.

5. Леспромхоз

Область, в которой может находиться машина, чтобы захватить конкретное дерево — это кольцо с радиусом от H — R до H + R (центр в P).
Нужно найти точку, которая попадает в максимальное количество колец.

Легко заметить, что оптимальный ответ будет среди таких точек:
  1) точки пересечения граничных окружностей
  2) по одной произвольной точке на каждой окружности
Доказывается так: рассмотрим оптимальную точку, если она не такая, будем двигать её или куда угодно, или по окружности, и получим такую точку с кратностью не хуже.
Всего O(N^2) пробных точек, каждая проверяется влоб за O(N).
Получаем решение за O(N^3).

3. Найти радистку

Сделаем два запроса:
? -10000 -10000 1 0
? -10000 -10000 0 1
Поскольку координаты цели небольше 1000 по модулю, цель точно расположена строго между ними.
Отношение уровня сигнала этих двух запросов даёт тангенс угла между осью координат и направлением на цель.

Затем можно сделать аналогичные два запроса из точки (-10000, 10000), например.
В результате получится два луча, которые гарантированно не параллельны.
Находим точку пересечения и округляем — это и будет положение цели.
Хватает 5 запросов, считая последний запрос на попадание в цель.

6. Кеширование приближений

Прежде всего, для каждой операции вместо данного tol посчитаем L — минимальный размер подходящего приближения:
  L = S * pow(1/tol, 0.25)
Теперь получается, что для операции нужно иметь приближение размера M >= L, при этом тратится время C * M + D.
На построение приближения размера M тратится A * M + B времени — сложных формул больше нет.

В варианте 1, когда кеширование отключено, для каждой операции надо строить приближение заданного размера L.
Что-то более точное строить смысла нет — всё равно на выброс.
Тогда ответ равен:
  ans =   sum { (A * L[i] + B) + (C[i] * L[i] + D[i]) }
        i=1..n


В варианте 2 можно хранить только одну кривую.
Нужно разбить все n операций на отрезки, такие что на каждом отрезке используется своё приближение, а между отрезками приближение перестраивается.
Запишем ДП:
  R[i] — минимальные затраты времени, чтобы а) покрыть первые i операций описанными выше "отрезками"
  (0 <= i <= n)                               б) выполнить первые i операций, так что перед i-ой операции приближение будет выброшено/перестроено

Рекуррентная формула пишется по достраиванию последнего "отрезка" от R[j] до R[i].
Очевидно, для него надо брать допустимое приближение минимального размера Hij:
  Hij =    max   L[k]
        k=j..i-1
При этом на построение этого приближения и на выполнение с ним всех операций на отрезке потребуется:
  Tij = (A * Hij + B) +   sum  (C[k] * Hij + D[k])
                        k=j..i-1
С этими значениями общая формула записывается так:
  R[i] = min (R[j] + Tij)
         j < i
Значения Hij и Tij можно довычислять за O(1) внутри цикла по j.
Получается решение за O(N^2) времени и с O(N) памяти.


В варианте 3 можно хранить сколько угодно приближений в кеше.
Легко понять, что в таких условиях можно построить все приближения заранее, а потом для каждой операции выбирать самое маленькое подходящее.
Следовательно, от порядка операций ничего не зависит: давайте отсортируем их по возрастанию размера L[i].
Теперь для первых операций используется первое приближение, затем в какой-то момент переключаемся на второе, затем на третье, и т.д.
То есть по сути после сортировки в кеше можно хранить только одно приближение, а значит задача свелась к предыдущей.

Запускаем в точности динамику из варианта 2, только после предварительной сортировки по L[i].
В ответ выводим, что все построенные приближения надо построить сразу, до первой же операции.

4. Код Морзе

Разобъём сигнал на элементы — отрезки одинаковых значений.
Будем решать динамикой, читая элементы по очереди.

Состояния динамики:
  R[k] — минимальное количество ошибок при расшифровке префикса из k элементов в полные слова
Переход — выбрать любое слово в словаре и добавить его.
При этом надо наложить закодированный вид слова на продолжение сигнала и посчитать количество ошибок.
Т.к. каждое слово из каждого состояния обрабатывается примерно за его длину, получаем:
  Память: O(N)      (N — количество элементов)
  Время: O(N D)     (D — суммарный размер словаря)

На самом деле, легко заметить, что если сигнал можно расшифровать, то количество ошибок при любом варианте расшифровке получается одинаковое.
Так что существенная часть задачи — это выбор лекс. минимального варианта текста.
Чтобы его найти, можно традиционно запустить динамику в обратном направлении:
  R[k] — минимальное количество ошибок при расшифровке суффикса, начинающегося с k-ого элемента, в полные слова
Переходы надо делать в сторону уменьшения k, и для каждого состояния сохранять лекс. минимальное слово, по которому в него пришли.
Тогда обратный ход восстановит лексикографически минимальный ответ.

Стоит заметить, что на многих тестах в этой задаче отлично работают всякие переборы с отсечениями.
Можно построить класс тестов, которые эквивалентны задаче о рюкзаке, ставя четыре минуса между одинаковыми буквами и задавая слова из той же буквы разной длины.
На таких тестах переборы работают плохо, так что хочется верить, что исчезающе мало переборов получило Accepted =)

8. Текстовый редактор

Если разобраться в механике процесса, то получается, что план должен состоять из 1) перемещений вверх/вниз и 2) переноса куска текста.
При переносе определяется, до какой позиции от текущий надо выделить кусок, и в какое именно место вставить.

Поскольку N довольно маленькое, можно решить задачу "влоб".
Составим граф состояний и переходов.
Состояние — это порядок строк текста плюс текущее положение курсора. Всего (N+1)! состояний (N = 8 -> 362880 штук).
Переходов из каждого состояния порядка O(N^2) — нужно перебрать две позиции. (N = 8 -> примерно 30 штук)
Далее на этом графе можно запустить алгоритм Дейкстры с кучей, получив решение за O((N+1)! * N^2 * N).

Концептуальных сложностей в этом нет, однако в задаче довольно жёсткие требования по скорости работы.

Поэтому нужно применить следующие оптимизации:
  1) Вместо того, чтобы складывать все состояния в map/dictionary, можно их все честно закодировать номерами от 0 до (N+1)!-1.
  2) Поскольку все расстояния и тайминги очень маленькие, то в алгоритме Дейкстры вместо кучи можно использовать набор списков.
    То есть для каждого числа k = 0..5000 хранить список всех вершин v, у которых D[v] = k.
  3) Порядок строк не влияет на структуру переноса, поэтому можно предподсчитать все переносы для каждого положения курсора.
    Получится O(N^3) переходов, для каждого можно заранее сохранить перестановку строк, стоимость, новое положение курсора.


В принципе, можно дополнительно оптимизировать алгоритм с помощью эвристики A*, хотя для получения Accepted это было НЕ обязательно.

Для этого нужно построить функцию оценки снизу расстояния до конечного состояния.
Пусть D элементов находятся не на своём месте.
Тогда необходимо сделать как минимум D нажатий клавиш вверх или вниз, чтобы "замести" эти строки — иначе не получится их изменить.
Теперь найдём "разрезы" — такие положения, что строка снизу и строка сверху в конечном состоянии НЕ должны тоже идти подряд в том же порядке.
Каждое наше перемещение режет текст в трёх местах и сшивает по-другому, а значит устраняет максимум три разреза.
Поэтому если есть K разрезов, то нужно как минимум roundup(K/3) перемещений, в каждом из них нужно нажать по одному разу все клавиши/комбинации кроме вверх/вниз.
Получается оценка:
  H(v) = D * min(Tup, Tdown) + roundup(K/3) * (Tshpr + Tshrel + Tctrlx + Tctrlv)
Можно показать, что эта оценка монотонная, то есть с ней алгоритм A* эквивалентен алгоритму Дейкстры с потенциалами, и все модифицированные веса неотрицательные.

2. Антиталия

Будем решать задачу методом движущейся плоскости: будем считать, Z-координату сечения "временем", и смотреть, как изменяется сечение.
В сечении всегда получается набор контуров (внешних/внутренних), ограничивающих плоскую область (или несколько плоских областей).
По мере увеливения Z структура контуров сохраняется, а точки в контурах движутся с некоторой скоростью — пока секущая плоскость не пройдёт через какую-нибудь вершину триангуляции.
Прохождение плоскости через вершину будем считать событием и обрабатывать особо.

В отличие от простых задач, где ответ всегда совпадает с каким-нибудь событием, в этой задаче оптимальное сечение может произойти между событиями (см. пример 2).
Заметим, что с течением времени (t = Z) каждая точка контура в сечении движется с постоянным вектором скорости, то есть координаты точек линейно зависят от времени.
Поскольку площадь контура считается как полусумма cross(P[i], P[i+1])/2, то получается, что площадь сечения зависит от времени квадратично.
Если для конкретного интервала между соседними событиями посчитать площадь как квадратичную функцию от Z, то найти её максимум на интервале будет легко:
надо лишь проверить значение в начале и в конце, а также в вершине параболы, если она находится внутри интервала.

К сожалению, отслеживать контуры в сечении очень сложно: контуры возникают, объединяются, разделяются и т.п.
На самом деле, это и не нужно: вклад каждого отрезка сечения в площадь сечения никак не зависит от окружающих объектов.
Действительно, каждый отрезок P->Q сечения добавляет cross(P, Q)/2 в общую площадь — главное верно определить направление отрезка, т.к. от этого зависит знак площади.
Оказывается, если сторона треугольника пересекает плоскость сверху вниз (т.е. Z убывает), тогда точка пересечения будет началом отрезка сечения, порождённого этим треугольником.
Другая сторона треугольника, которая пересекает плоскость снизу вверх (Z возврастает), будет концом этого отрезка.
Третья сторона в сечении отсутствует: они либо полностью сверху, либо полностью снизу плоскости.
Разумеется, здесь подразумевается, что стороны направлены в порядке обхода, указанном в файле.

Таким образом, получается довольно простое решение.
Выпишем все события (т.е. вершины сетки) в один большой массив, отсортируем их по времени.
Далее обрабатываем события по порядку, все одновременные события обрабатываем одной группой.
Сначала для всех треугольников, инцидентных всем вершинам в текущей плоскости, "выключаем" старый отрезок, а затем для всех этих же треугольников считаем и "включаем" новый отрезок.
Вклад каждого отрезка-треугольника в площадь лучше хранить в массиве, тогда выключение — это просто зануление соотв. элемента этого массива.
При включении нужно представить, что секущая плоскость чуть выше рассматриваемой плоскости, понять, как устроен отрезок сечения, и посчитать векторное произведение движущихся точек.
Разумеется, если треугольник/отрезок уже включен, то включать его повторно не надо, чтобы не учесть его вклад в площадь дважды.
Текущую площадь как квадратичную функцию можно хранить в глобальной переменной: при выключении отрезка вычитать его старую функцию, а при включении добавлять новую функцию.

Если предподсчитать списки инцидентных вершинам треугольников заранее, то весь алгоритм будет работать за O(N log N).


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

Тем не менее, есть ряд способов кардинально улучшить точность решения в разных ситуациях (ни один из них НЕ был нужен, чтобы получить Accepted):
1) Хранить квадратичные функции для треугольников не в обычном массиве, а в дереве отрезков на сумму, при изменении честно пересчитывая все узлы до корня.
  Это позволяет полностью избежать накопления погрешности, а кроме того снижает погрешность суммирования в целом (см. https://en.wikipedia.org/wiki/Pairwise_summation).
2) Вычислять для отрезка cross(P, Q-P) вместо cross(P, Q): помогает для тонких тел вдали от начала координат по X/Y.
3) Вычислять квадратичные функции не от переменной Z, а от смещения (Z — O), где O — это например Z-координата вершины треугольника, при рассмотрении которой вычислялась эта функция.
  Это сильно повышает устойчивость представления квадратичных функций для коротких по Z треугольников на большом расстоянии от Z == 0.
  Правда при сложении функций с разными O в дереве отрезков нужно делать дополнительную конвертацию.