Тренировки

1 комментарий
Подписаться на комментарии к посту

A. входы располагаем в той же последовательности что и станции, ГМТ точек вход в первую станцию расстояние между станциями, такое чтобы и первая точка и k-аяпопали в необходимые интервалы, образуют отрезок, нужно понять есть ли пересечение у всех этих отрезков.

B. Ленивая динамика по делителям, перебирая цифру.

С. Можно либо идти в прямую пользуясь формулой Эйлера (и при этом считая число компонент связности из ребер) или же в обратном направлении удаляя разрезы. Надо будет уметь объединять множества.

D. Стандартная задача на двумерное дерево интервалов. в каждой вершинке дерева по отрезку по первой координате храним дерево с ответами для вторых координат

E. К каждой координате добавляем направление, стоимость движения прямо оцениваем в 0, поворота в 1, далее специальный поиск в ширину или дейкстра решат задачу.

F. Нужно было писать перебор с отсечениями, отсекаем по величине наибольшего простого (сумма будет не меньше его + N-1), далее перебираем значение минимального поочередно, пользуясь оценкой с предыдущего шага и ограничением сверху усредненной суммой, заодно проверяя сравнение со средним геометрическим. Для двух решаем квадратное уравнение. Так же можно сгенерить список всех делителей не делящихся на наименьшее простое и когда всю степень его уже выберем из p бегать только по этому списку (или в процессе перебора удалять и возвращать неделящиеся).

G. Пишем Rope или декартово дерево, находим конечный порядок и по нему считаем расстояния.

H. (B-A+1)(A+B) = 2S собственно перебираем все делители 2S и находим A и B

I. строим дерево из символов строк, запоминая сколько раз мы побывали в каждой вершине и просто бегаем по нему

J. Заметим, что если оба числа меньше 200, то мы успеваем решить задачу возведением в степень, если же одно из чисел больше 200, то мы применяли такой шаг не более 5000000 раз, перебирая это значение и используя формулу с числом сочетаний получаем ответ.