Командная тренировка №6 (27.08.2013, NCPC 2012)

Участники тренировки

• Андрей Корнеев
• Владимир Фолунин
• Александр Ерофеев (организатор)

Соревнование

Nordic Collegiate Programming Contest 2010 (Preliminary contest for North-Western Europe Programming Contest, 2012 год, Дания, Финляндия, Исландия, Норвегия, Швеция). Для прохода в NWERC требовалось решить 7 задач.

Зеркало соревнования

Задачи и комментарии

• A. Aaah! (решена на тренировке)

• B. Bread Sorting (решена на тренировке)

Поиск числа инверсий в перестановке

Искать можно деревом отрезков или деревом Фенвика: на шаге i считаем сумму на отрезке [i..n] и выставляем i-й элемент в 1.

• C. Cookie Selection

• D. Doorman (решена на тренировке)

• E. Eco-driving

Бин. поиск по углу, затем ищем кратчайший путь при выбранных ограничениях.

• F. Food review

• G. Galactic Warlords (решена в дорешивании)

Код решения.

• H. Horror List (решена на тренировке)

• I. Infiltration

• J. Juice

Жадное решение. Перебираем дома в порядке увеличения требования по потреблению

• K. Kindergarten

Сведение к 2-SAT : для каждого ребенка заведем переменную, ее значение будет true если к одному из учителей, false если к другому, условиям будут соответствовать нежелательные пары из входных данных. Какие пары сочтем нежелательными, переберем бинарным поиском.

• L. Luggage

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