Тренировки

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

basil-ast
4 октября 2013, 21:44

Провожу я, Астахов Василий, +79263460215. Начало в 12. Не опаздывать:) в бц морозов, 7 этаж

http://acm.math.spbu.ru:8087/~ejudge/team.cgi?contest_id=010050

Имена входных файлов

A. antipal.in, antipal.out

B. bricks.in, bricks.out

C. cactus.in, cactus.out

D. decimation.in, decimation.out

E. forum.in, forum.out

F. queries.in, queries.out

G. routes.in, routes.out

H. solitaire.in, solitaire.out

I. square.in, square.out

J. wheels.in,wheels.out

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

В задаче Е тире ето "-" ?

Выкладываю разбор сейчас, кто не закончил просьба не читать!:

А. Стандартная задача про билеты. Решаем про количество

 

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

 

C. Вначале кактус надо разложить подвешенно на циклы и ребра. Далее мы будем вычислять числа Гранди для различных подграфов, в качестве подграфов будут: вершина и весь ее подкактус, вершина и некоторая цепочка из циклов, возникающая при удалении ребра. Аккуратно все линейно пересчитываем.

 

D. Динамика - наилучший ответ если мы поставили i обычных людей и j безбилетников. Переход совсем несложный (мы ставим сейчас или обычного или безбилетника)

 

E. В задаче надо сделать то что просят (то есть выделить сколько слов trolleybus и tram в сообщении)

 

F. Самой простой вариант хранить в  числу людей список с номерами городов и делать по нему бинпоиск. Или можно отсортировать все запросы по правой границе, бежать слева направо и хранить для каждого числа людей самый правый встреченный такой город.

 

G. Конструктивная задача. Заметим что если построим последовательность такую что a[i+1]-a[i] a[z+1]-a[z] не сравнимы по модулю 2*n, то нам подойдут маршруты вида (a[i]+j) % 2*n. В качестве такой последовательности можно взять 2*n 1 2*n-1 2 2*n-2 3...

 

H. (n^2+ 3*n -2) / (2*n*(2*n-1)), в общем-то формула подбирается по первым значениям, если предположить знаменатель, строго доказательства у меня пока нет, но видимо можно индукцией

 

I. Ограничения позволяют пересечь образ каждого квадрата из первого и квадрат из второго множества и посчитать их общую площадь. Соответственно надо аккуратно написать геометрию пересечения двух равных квадратов.

 

J. Надо по каждому размеру сложить число встреч этого числа div 4