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