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

Материал из Олимпиадное программирование в УлГТУ
Версия от 17:28, 27 августа 2013; 89.239.158.95 (обсуждение) (→‎Задачи и комментарии)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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

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

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
Для каждой пары чемоданов найдем все интервалы скоростей, при которых они столкнутся. Отсортируем все отрезки и наидем максимальную скорость, при которой ничего не сталкивается.