http://opencup.ru/

Да уж. Мы глупые(

Прямо как у нас решение:D

D: Чтобы понимать в какую часть мы попадаем на i-ом разделении нужно смотреть i-ый слева бит числа k - 1. При этом последние примерно 60 битов проверяем ручками, а среди первых n - 60 — все биты 0, а значит [(n — 60 + 1)/2] раз добавится к A, и [(n — 60)/2] к B.

H: Общий случай: пусть компания получила p%, тогда 2p% = (после сокращения) поставлено на проигравших и на победителей. У нас ограничения только сверху, поэтому можно считать, что всего ставок y, теперь если y - x > k или k·(n - 1) < x, то все плохо, иначе все хорошо распределяется.

Осталось понять, что 50% получить невозможно, а 100% соответствует нашему решению для 50% — 0 поставлено на победителя.

А: сначала решим такую подзадачу: для числа n посчитать f(n) — число способов разбить на 3 неупорядоченных слагаемых. Это . Первое слагаемое получено по формуле включения-исключения и включает варианты, когда все 3 числа различны, второе слагаемое — когда среди трех есть совпадающие.

Дальше, учитывая, что f(n) не убывает, используем бинарный поиск для нахождения обеих границ. Ответ — некоторый подотрезок натурального ряда.

J: Про каждого человека, когда мы его берем в текущий состав, достаточно понимать, сколько подряд единиц у него с этого момента(чем больше, тем лучше), ибо его все равно перед его нулем нужно убрать и лучше, чтобы он мог продержаться как можно больше.

Теперь решение: сперва динама dp[man][pos] сколько с этого момента единиц у человека. Потом выбираем k лучших по dp[man][0] и на каждом шаге проверяем, что в команде все с dp[man][pos] > 0, выкидываем худшего на данным момент и выбираем лучшего из тех, кто не в команде.

E: Вероятность сменить позицию у встречных людей с L->R или с R->L это . Дальше вроде понятно все. Считаем вероятность нахождения слева и справа для нас и к матожиданию в силу линейности прибавляем вероятности столкновения.

Case with P = 100 and any N and K.

Например так.

Сначала наивное решение. Построим 3 бора, в каждом боре в вершине сохраним сет номеров строк. Тогда каждый запрос характеризуется тройкой чисел — номерами вершин в 3 борах. Ответ — это размер пересечения трех сетов.

Теперь корневая оптимизация. Для каждой вершины бора, если размер сета больше sqrt(N), то заменим его на битсет. То есть вершина бора у нас будет примерно такой:

struct Node {
   set <int> s;
   bitset <N> * bs;
};

В итоге имеем, что каждая вершина бора или "тяжелая" (а таких не больше корня, то есть памяти нам хватит), или "легкая" (их суммарный размер не больше 10⁵ по условию). Значит, памяти хватает.

Теперь при ответе на запрос если у нас во всех 3 вершинах сеты, то просто используем set_intersection(), если все битсеты — то используем побитовый and битсетов и используем bs->count(), а если есть и сеты, и битсеты, то пересекаем сеты, а потом проходимся по сету и проверяем, есть ли элемент в битсете.

Вроде это работает за O(Nsqrt(N)) — на онсайте за секунду зашло.

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

Для каждого из 3 полей сохраним все возможные его строчки и запросы в боре. Занумеруем вершины каждого бора в порядке обхода dfs'а. Теперь каждый ID туриста характеризуется 3 числами — позициями соответствующих вершин в порядке обхода, назовем их x, y, z, тогда ID будет точкой в трехмерном пространстве. Запрос так же характеризуется 3 вершинами, и ответом на запрос является число таких ID, что соответствующие ему вершины лежат в 3 поддеревьях вершин запроса. Так как мы пронумеровали все вершины бора в порядке обхода, то в одном поддереве будут лежать вершины с последовательными номерами от L до R. Зная такие границы для каждой вершины, можно ввести ограничения на каждую координату искомых точек и свести запрос к задаче нахождения количества точек внутри параллелепипеда.

Ну эту задачу вроде уже можно решать разными способами, например, оффлайн деревом отрезков декартовых деревьев:)

А чем интересней? Прибавим ко всем единичку, а потом тоже самое.

There was clarification, that there should be at least 1 bet

At least must be one i that A[i] >= 1.

P.S. If you write in english write not to russian thread (it's second time).

for example
1
1 0 0.. 0

Участников Petr team слегка раскидало по миру просто

I: Drawing some cases you can notice that no car need to go back ever because of two-lane first and last segments. The most effective way to avoid accident is always such: one of the car need to stop in the last but one (in its direction) X-coordinate of two-lane segment before the accident place, after stop it waits a moment when another car "touch" it (look at first case on the second picture in statement) and starts moving. Also you can notice that R doesn't influence to anything, so you can ignore it. So, we have some states (maybe more — depends on implementation): 1) first car is in A-point and second car somewhere at the road, 2) second car is in B-point and first car somwhere at the road. Moving from one state to another is simple — O(log(L)). Number of states is not big and you can easily find (using simple modelling) result for period from zero-time till the time some state firstly occured. When some state occured for the second time — it's a cycle. You just need to find number of cycle repeat and to do a modelling for remaing time. Complexity: O(cycle_length * log(L)).