Если хотя бы для одного участника beforei ≥ 2400 и afteri > beforei, то ответ "YES", иначе "NO"
Ограничения в этой задаче таковы, что можно перебрать a от 0 до n / 1234567 и b от 0 до n / 123456, и проверить, что n - a * 1234567 - b * 123456 не отрицательно и делится на 1234.
Если хотя бы одна такая пара чисел a и b нашлась, то ответ "YES", иначе "NO"
Будем решать эту задачу жадно. Выполняем оставшиеся запросы в порядке, в котором они нам даны.
Если текущий запрос – insert x, то добавим элемент x в кучу.
Если текущий запрос – removeMin, то если куча не пуста, то просто удалим минимум, а если куча пуста, то вставим запрос insert x, где x – любое число, и затем выполним removeMin
Если текущий запрос – getMin x то выполним следущее:
- Пока куча не пуста и минимальный элемент в ней меньше x, выполним запрос удаления минимума из кучи.
- Если куча пуста или минимальный элемент в ней не равен x, выполним запрос insert x.
- Выполним запрос getMin x.
Для того, чтобы уложиться в ограничение по времени, необходимо использовать структуру данных, которая поддерживает выполнение описанных операций за время O(logN), где N – количество элементов. Например, можно было использовать, std::priority_queue или std::multiset.
Формальная постановка задачи:
Дан ориентированный граф без циклов, в каждую вершину входит не более одного ребра (лес "ориентированных деревьев"). Вершина A является предком вершины B, если из A есть путь в B. Также каждая вершина является предком самой себя.
Каждой вершине i сопоставим вершину ai, причем ai – предок i.
Необходимо построить последовательность вершин, такую что для любой вершины i самая первая вершина в последовательности, являющаяся предком i, была равна вершине ai. Либо сказать, что такой последовательности не существует.
Решение:
Рассмотрим последовательность ans, содержащую по одному разу все вершины, встречающихся в последовательности an, и только их. Расположим элементы этой последовательности так, чтобы для любых i и j если ansi – предок ansj, то i ≥ j.
Если эта последовательность является ответом, то выведем её. Иначе, ответа не существует.
Почему это так.
Если какая-то вершина ai из последовательности a не встречается в ans, то мужчина, который должен подарить подарок мужчине с номером ai, не сможет этого сделать. Значит каждая вершина ai должна быть в результирующей последовательности.
Если ai -- предок aj и i < j, то мужчина, который должен подарить подарок мужчине с номером aj не сможет этого сделать.
Как получить такую последовательность?
Получим топологическую сортировку вершин графа, то есть такую последовательность вершин, в которой каждый предок идет первее любого своего потомка, затем развернем её и выбросим все лишние вершины.
Как проверить, что последовательность является ответом?
Давайте вычислим, кому будет дарить подарок каждый мужчина. Изначально для каждого мужчины мы не знаем, кому он будет дарить подарок. Переберем вершины результирующей последовательности по порядку.
Для всех вершин (мужчин) из поддерева текущей вершины (т. е. для вершин, для которых текущая вершина является предком), для которых мы не знаем, кому эта вершина (мужчина) будет дарить подарок верно, что эти вершины будут дарить подарок текущей вершине, потому что текущая вершина – самый первый их предок из списка.
Пройдем dfs'ом по всем этим вершинам и запомним в них, кому будет подарен подарок.
После того как мы выполним эту операцию для всех вершин результирующей последовательности, сравним для каждой вершины графа актуальную вершину, которой мы будем дарить подарок, и требуемую. Если есть хотя бы одно несовпадение, то ответа не существует.
Для начала разберем случай, когда таракан в момент старта уже находится внутри или на границе какого-то круга. В этом случае, таракан всегда спасется, т. е. вероятность равна 1.
Иначе у таракана есть время, чтобы добежать в любую точку круга с центром в точке x0, y0 радиуса v × t.
Переберем все круги-тени и для каждого поймем как соотносится этот круг с кругом достижимых точек таракана. А именно, найдем максимальный допустимый угол, такой что выбрав направление из этого угла таракан успеет спастись, добежав до текущего круга.
Вообще говоря, максимальный угол, выбрав направление из которого таракан за бесконечное время добежит до круга, – это угол, образованный двумя касательными из точки старта таракана к окружности. Если длины этих касательных не превосходят v × t, то этот угол и будет являться искомым углом для текущего круга.
Иначе найдем точки пересечения границы "тараканьего круга" и границы текущего круга (т. е. пересечем две окружности). Если точек пересечения нет, или она одна (окружности касаются), то текущий круг слишком далеко от таракана. Иначе точки пересечения и точка старта образуют искомый угол для текущего круга.
После того как нашли все углы понимаем, что это отрезки, покрывающие отрезок от 0 до 2π. Сортируем их начала и концы и находим длину объединения этих отрезков. Длина объединения, деленная на 2π, дает нам искомую вероятность выживания.
