Разбор задач КРОК 2016 — Квалификация

Правка ru6, от fcspartakm, 2016-04-18 18:47:12

Лучше поздно, чем никогда...

644A - Parliament of Berland

Из условия задачи следует, что либо демократов и республиканцев поровну (если n чётно), либо демократов на одного больше (если n нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные.

Таким образом, если n > a·b, ответом будет  - 1. В противном случае рассадка всегда найдется.

Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в i-й строке и j-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если (i + j)mod2 = 0, значит соответствующая клетка должна быть белой, иначе чёрной.

Пример решения

644B - Processing Queries

Для решения данной задачи очень удобно воспользоваться структурой данных, которая называется очередь.

Очередь — это структура данных со следующим принципом доступа к элементам: «первый пришёл — первый ушёл». Добавление элемента (\textit{push}) возможно лишь в конец очереди, а взять элемент из очереди можно только из её начала (\textit{front}). Удалить элемент можно также только из начала очереди (\textit{pop}).

В данной задаче нужно было перебрать все запросы в хронологическом порядке. Будем хранить в очереди времена окончания обработки запросов. Для текущего запроса, пока в начале очереди находятся запросы, которые закончат обрабатываться не позднее, чем появился текущий запрос, нужно просто удалять их из начала очереди, так как они никак не повлияют на текущий. Если после этих действий размер очереди равен максимальному допустимому числу, ответ для текущего запроса  - 1. В противном случае, нужно добавить время окончания обработки текущего запроса в очередь, вывести это время и продолжить алгоритм.

Пример решения

644C - Hostname Aliases

Для решения данной задачи воспользуемся структурами данных map и set. Переберем все имеющиеся адреса страниц, затем получим hostname и path для каждого адреса, и добавим текущий path в множество путей для текущего hostname (для этого будет нужен map, где ключом будет строка hostname, а значением — множество строк path).

Осталось только объединить все hostname, множества путей которых совпадают (это можно сделать с помощью map, где ключом будет множество строк path, а значением — вектор строк hostname), и вывести те группы, размер которых больше единицы.

Пример решения
Теги крок-2016, квалификация, разбор

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru7 Русский fcspartakm 2016-04-18 18:47:32 24 Мелкая правка: 'Лучше позд' -> '### Your title here...Лучше позд' (опубликовано)
ru6 Русский fcspartakm 2016-04-18 18:47:12 28 Мелкая правка: '----------### [probl' -> '----------\n### [probl'
ru5 Русский fcspartakm 2016-04-18 18:47:05 1010
ru4 Русский fcspartakm 2016-04-18 18:44:20 1626
ru3 Русский fcspartakm 2016-04-18 18:42:43 23 Мелкая правка: 'и $(i + j)~mod,2016-04-18~2 = 0$, зн' -> 'и $(i + j) mod 2 = 0$, зн'
ru2 Русский fcspartakm 2016-04-18 18:41:12 23 Мелкая правка: 'и $(i + j) mod 2 = 0$, зн' -> 'и $(i + j)~mod~2 = 0$, зн'
ru1 Русский fcspartakm 2016-04-18 18:40:56 1437 Первая редакция (сохранено в черновиках)