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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
 
Строка 23: Строка 23:
* F. Food review  
* F. Food review  
: '' ''
: '' ''
* G. Galactic Warlords
* G. Galactic Warlords (<span style="color: green;">'''решена в дорешивании'''</span>)
: '' ''
: ''[http://pastebin.com/0zi6h3iS Код решения]. ''


* H. Horror List (<span style="color: green;">'''решена на тренировке'''</span>)
* H. Horror List (<span style="color: green;">'''решена на тренировке'''</span>)

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