Командная тренировка №6 (27.08.2013, NCPC 2012): различия между версиями
Перейти к навигации
Перейти к поиску
(Новая страница: «== Участники тренировки == * Андрей Корнеев * Владимир Фолунин * Александр Ерофеев (организ…») |
|||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 13: | Строка 13: | ||
: '' '' | : '' '' | ||
* B. Bread Sorting (<span style="color: green;">'''решена на тренировке'''</span>) | * B. Bread Sorting (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: '' '' | : ''Поиск числа инверсий в перестановке'' | ||
: ''Искать можно деревом отрезков или деревом Фенвика: на шаге i считаем сумму на отрезке [i..n] и выставляем i-й элемент в 1.'' | |||
* C. Cookie Selection | * C. Cookie Selection | ||
: '' '' | : '' '' | ||
| Строка 19: | Строка 20: | ||
: '' '' | : '' '' | ||
* E. Eco-driving | * E. Eco-driving | ||
: '' '' | : '' Бин. поиск по углу, затем ищем кратчайший путь при выбранных ограничениях.'' | ||
* 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>) | ||
| Строка 32: | Строка 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]] | ||
Текущая версия от 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
- Для каждой пары чемоданов найдем все интервалы скоростей, при которых они столкнутся. Отсортируем все отрезки и наидем максимальную скорость, при которой ничего не сталкивается.