Тренировки

Тренировка в субботу 14.12

basil-ast
13 декабря 2013, 16:03

Тренировку провожу я, Астахов Василий, +79263460215, время начала 12:00

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

Решаем NWERC 2013,

Входные данные первого теста задачи I:

--34
+1234
--09
+111111111111
--0071

A. Надо найти минимальный остов - в нем точно ребра исходного графа + найти минимальное ребро, лучше чем путь между вержинами по дереву.

B. В планарном графе полных подграфов довольно мало (не более линии от числа ребер) потому их можно все по-тихоньку перебирать и выбрать наилучший. для ускорения можно использовать битовые операции.

С. Простая динамика, вероятности оказаться в конкретной позиции.

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

E. извлекаем степень из a, приходим к случаю скольким способом число вида l * b^c можно представить в подобном виде(z* x^y), раскладываем b и l по степеням простых, перебираем теперь y (2..200000) и считаем число подходящих x (для каждого ещё предпосчитываем число дальнейших представлений y в виде башни)

F. Нужно посчитать номер дня по юлианскому календарю, прибавить один и найти дату по грегорианскому

G. Геометрия на пропорции и теорему пифагора

H. Заметим, что в каждый момент на хайвее находится не более 100 * log(100) различных машин, таким образом переская новую с каждой из предыдущих можно найти максимальную точку

I. Кубическая динамика по отрезкам

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