Командная тренировка №6 (27.08.2013, NCPC 2012): различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 20: Строка 20:
: '' ''
: '' ''
* E. Eco-driving
* E. Eco-driving
: '' ''
: '' Бин. поиск по углу, затем ищем кратчайший путь при выбранных ограничениях.''
* F. Food review  
* F. Food review  
: '' ''
: '' ''
Строка 33: Строка 33:


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


* K. Kindergarten
* K. Kindergarten
: '' ''
: '' Сведение к [http://e-maxx.ru/algo/2_sat 2-SAT] : для каждого ребенка заведем переменную, ее значение будет true если к одному из учителей, false если к другому, условиям будут соответствовать нежелательные пары из входных данных. Какие пары сочтем нежелательными, переберем бинарным поиском.''
* L. Luggage
* L. Luggage
: '' ''
: '' Для каждой пары чемоданов найдем все интервалы скоростей, при которых они столкнутся. Отсортируем все отрезки и наидем максимальную скорость, при которой ничего не сталкивается. ''
[[Category:Командные тренировки — 2013]]
[[Category:Командные тренировки — 2013]]

Версия от 12:32, 27 августа 2013

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

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

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

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