Тренировки

3 комментария

moscow66
Moscow SU Zvezdochka: Lakhtanov 

moscow69

Moscow SU Psychedelic Warlords: Klenin, Korikov, Tkachenko

A. Решается обычным деревом интервалов, только в вершинах храним битсет имеющихся значений и операция xor

B. Ответом будет n-1, простейший вариант просто соединять i авиакомпанией вершину i с более поздними

С. Разбиваем все на отрезки, в каждом отрезке вероятность выигрыша i-го выписывается в качестве интеграла от многочлена, сам многочлен имеет вид произведения одночленов и может за N*2 быть вычислен для каждого фиксированного победителя

D. Геометрически несложно показать, что ответ вершина A.

E. Перебираем все ответы по модулю 16*5*7*9*11*13 = 720720 и для каждого смотрим подходит ли под ответ

F. Делимость на 11: нужно посчитать знакочередующуюся сумму цифр по модулю 11, соответственно нужно понимать какие суммы по моудлю 11 мы можем получить использовав L минимальных цифр и K раз -. Дальше по каждой цифре для текущего баланса макзимизируем префикс, если можем добрать оставшееся

G. Нужно аккуратно разобрать когда можно достроить (в случаях когда мы увеличиваем первую цифру, вторую и любую из следующих), операции осуществляем с сетом.

H. Выкидываем гостей знающих менее K людей и не знающих менее K людей, обновляем, достаем минимум из кучи.

I. Решаем задачу на дереве с помощью чисел Гранди в случае если проигрывает тот кто не может сделать ход, теперь рассмотрим все прикорневые вершины, если в каждом из них функция гранди 0, и их нечетно то побеждает второй, иначе первой режа первое прикорневое ребро(а дальше играя симметрично)

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

J. Надо найти наиболее тяжелую антицепь, это можно сделать динамикой (какая максимальная антицепь если она заканчивается в этой вершине)

K. Нужно отсортировать a_i и b_i и вывести сумму.

L. Нужно научится определять координаты в стандартной записи и повертеть прибавку x,y