Original Mighty Morphin Power Rangers by Yurtigo
19 марта прошёл разогревочный раунд нашего чемпионата по спортивному программированию Russian Code Cup 2017. Этот раунд не влияет на итоговые результаты, но позволяет познакомиться с системой чемпионата и его задачами. Сегодня мы хотим рассказать об итогах раунда и разобрать его задачи:
A. Космический корабль
B. Рейнджеры в автобусе
C. Волшебное оружие
D. Рыцари и лжецы
E. Параллелепипед
На раунд зарегистрировалось 2789 человек, это в два раза больше, чем в прошлом году. Только один из них смог решить все пять предложенных задач! Поздравляем Михаила Ипатова. Ещё четыре человека справились с четырьмя из них. Самым популярным языком оказался GNU C++ 14. На нём отправили 565 решений задач. Второе и третье место заняли Python 3.5 (525 решений) и GNU C++ 11 (409 решений).
A. Космический корабль
Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Космический рейнджер оказался на инопланетном космическом корабле в окружении врагов. Чтобы освободиться, ему необходимо уничтожить всех врагов в определённом порядке.
Вокруг рейнджера n врагов, i-й из них обладает силой fi. Чтобы выбраться, рейнджеру необходимо уничтожить всех врагов, причём в таком порядке, чтобы сила последнего уничтоженного врага была равна сумме сил всех остальных врагов.
В запасе у рейнджера мало времени, так что он не успевает понять, как это сделать. Ему необходима ваша помощь. Восстановите порядок, в котором нужно уничтожать врагов, чтобы выбраться.
Входные данные
В первой строке ввода находится натуральное число n — количество врагов (2 ≤ n ≤ 105).
Во второй строке находятся n целых чисел fi, задающих силу каждого врага ( –109 ≤ fi ≤ 109).
Выходные данные
Выведите числа fi в порядке, в котором необходимо уничтожать соответствующих им врагов. Если существует несколько подходящих вариантов, выведите любой. Гарантируется, что хотя бы один подходящий порядок уничтожения существует.
Заметим, что если сила босса равна x, то сумма сил всех врагов равна 2x. Следовательно, чтобы найти силу босса, необходимо посчитать суммарную силу всех врагов и разделить её на 2. После этого необходимо найти какого-нибудь врага с такой силой и поменять это значение в массиве f со значением последнего врага.
B. Рейнджеры в автобусе
Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Космические рейнджеры едут на тайную встречу в автобусе.
Главный злодей внимательно следит за автобусом, в котором, по его мнению, едет кто-то из рейнджеров. В салоне n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и злодей знает, кто на какое место сел и в каком порядке. Исходно все места были свободны.
Злодею известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:
- Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
- Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, синий садится справа.
- Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
- Жёлтый рейнджер тоже любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
- Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.
Главный злодей хочет узнать, кто из k пассажиров мог бы быть каждым из рейнджеров. По известным местам, куда садились пассажиры, выведите эту информацию. Обратите внимание, что совсем необязательно все рейнджеры ехали на этом автобусе.
Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 109, 1 ≤ k ≤ min(2•105, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа xi и yi — место, на которое сел i-й пассажир (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2), xi — это номер ряда, yi = 1, если это место слева от прохода, и yi = 2, если справа.
Все места, на которые сели пассажиры, различны.
Выходные данные
В первой строке выведите число s1 — количество пассажиров, которые могли бы быть красным рейнджером, а затем, через пробел, s1 чисел — номера этих пассажиров в порядке возрастания (пассажиры нумеруются с 1 по k в том порядке, в котором они заданы во входном файле).
В следующих четырёх строках выведите в том же формате информацию об остальных рейнджерах: синем, чёрном, жёлтом и розовом.
Будем обрабатывать пассажиров по очереди и для каждого определять, кем он мог бы быть. Сразу заметим, что розовый рейнджер может сесть куда угодно, поэтому любой пассажир может быть им.
Для каждого места надо помнить, свободно ли оно. Заведём unordered_set, в котором будем хранить занятые места. Проверим, мог бы очередной пассажир быть красным рейнджером. Для этого найдём место, на которое сел бы красный. Переберём циклом ряд от 1 до n. Если попался ряд, в котором есть свободное место, выбираем левое, если оно свободно, или правое, если нет — это и будет место, куда сел бы красный. Поскольку он выбирает место однозначно, мы можем определить, мог бы этот пассажир быть красным — нужно проверить, что он сел именно на это место. Таким же образом узнаём, куда сели бы синий, жёлтый и чёрный: разница в порядке перебора рядов (от 1 до n или наоборот) и в порядке выбора места в ряду (сначала левое или правое). После обработки пассажира отметим его место как занятое.
Решение работает за O(nk) и использует O(k) памяти.
Чтобы улучшить решение, заметим, что каждый из циклов останавливается, когда находит ряд, в котором есть свободное место. Это означает, что нужно быстро отыскивать первый и последний незанятые ряды. Будем поддерживать эти значения — first и last. Изначально first = 1, last = n. После каждой итерации цикла обновим эти значения. Будем увеличивать first на 1, пока ряд first занят, затем уменьшать last на 1, пока ряд last занят. Занятых рядов не может оказаться больше k / 2, поэтому first и last сделают O(k) шагов. Таким образом, улучшенное решение работает за O(k) и проходит все тесты.
C. Волшебное оружие
Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Для сборки волшебного оружия необходимо соединить три фрагмента: зелёный, красный и синий.
Зелёному, красному и синему рейнджеру стало интересно, сколько у них есть различных способов собрать волшебное оружие. Известен набор фрагментов каждого рейнджера. У зелёного рейнджера есть зелёные фрагменты, у красного рейнджера — красные, а у синего — синие.
При сборке оружия необходимо соблюдать три правила:
- Первая цифра номера модели красного фрагмента должна быть равна последней цифре модели зелёного.
- Последняя цифра номера модели красного фрагмента должна быть равна первой цифре модели синего.
- Все три использованных фрагмента должны иметь разные номера моделей.
Два способа собрать оружие считаются различными, если хотя бы один из рейнджеров использует при сборке другой фрагмент, возможно, той же модели. Вам известны номера моделей фрагментов каждого рейнджера. У одного рейнджера может быть несколько фрагментов одной модели. Помогите рейнджерам понять, сколько у них есть различных способов собрать оружие.
Входные данные
В первой строке ввода заданы числа g, r и b — количество фрагментов у зелёного, красного и синего рейнджера, соответственно (1 ≤ g, r, b ≤ 105).
В следующей строке находится g чисел xi — номера моделей, которые есть у зелёного рейнджера (0 ≤ xi ≤ 109).
В следующей строке находится r чисел yi — номера моделей, которые есть у красного рейнджера (0 ≤ yi ≤ 109).
В следующей строке находится b чисел zi — номера моделей, которые есть у синего рейнджера (0 ≤ zi ≤ 109).
Выходные данные
Выведите одно число — количество способов собрать оружие.
Предпочитаем массивы: R[a][b] — количество фрагментов у красного рейнджера, у которых первая цифра равна a, а последняя равна b; G[a] — количество фрагментов у зелёного рейнджера, у которых последняя цифра равна a; и B[b] — количество фрагментов у синего рейнджера, у которых первая цифра равна b.
Если бы у разных рейнджеров не было одинаковых моделей фрагментов, ответ был бы равен сумме по всем a и b значений G[a]•R[a][b]•B[b].
Чтобы учесть ситуацию, когда у какой-то пары совпадают модели, посчитаем количество пар фрагментов с одинаковым номером модели у красного и синего, красного и зелёного и синего и зелёного рейнджеров, соответственно (например, с помощью std::map). Заметим, что подходят только номера, у которых первая и последняя цифра совпадают. Воспользуемся формулой включений-исключений, вычтем из ответа число таких пар и добавим удвоенное количество троек фрагментов, когда у всех трёх рейнджеров совпадают модели.
D. Рыцари и лжецы
Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Космический рейнджер построил свою армию в две шеренги по k солдат. Соседями в данном построении он считает солдат слева и справа в той же шеренге, а также солдата, который стоит на той же позиции, но в другой шеренге. Рейнджер знает, что в армии есть рыцари, которые всегда говорят правду, и лжецы, которые лгут, отвечая хотя бы на один вопрос, который им задали.
Рейнджер выбрал один или два вопроса из множества:
- «Правда ли, что ровно x из твоих соседей рыцари?»
- «Правда ли, что ровно y из твоих соседей лжецы?»
И задал каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Внезапно все солдаты ответили «да» на все заданные им вопросы. Теперь космического рейнджера интересует, какое минимальное и максимальное число рыцарей может быть в его армии. Помогите ему выяснить это. Разберем второй пример из условия: в каждой шеренге по пять солдат, были заданы вопросы «Правда ли, что ровно один из твоих соседей рыцарь?» и «Правда ли, что ровно двое из твоих соседей лжецы?»
Армия может полностью состоять из лжецов (они точно солгали, отвечая на первый вопрос, хотя крайние в шеренгах ответили правду на второй вопрос). В этом случае достигается минимальное число рыцарей — 0. Другой вариант: в каждой шеренге на втором и четвёртом местах стоят рыцари, а на остальных — лжецы. В этом случае все рыцари говорят правду, как и должны, а каждый лжец говорит неправду, отвечая на второй вопрос (у каждого лжеца ровно один сосед — лжец). В этом случае достигается максимальное число рыцарей — 4.
Входные данные
В единственной строке ввода содержится три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 105, –1 ≤ x, y ≤ 3).
Если x = –1, это означает, что рейнджер не задавал первый вопрос.
Если y = –1, это означает, что рейнджер не задавал второй вопрос.
Гарантируется, что рейнджер задавал хотя бы один вопрос.
Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите –1.
Иначе первая строка должна содержать одно число — наименьшее возможное количество рыцарей в армии, а вторая — наибольшее возможное количество рыцарей в армии.
Будем решать задачу динамическим программированием по профилю. Найдём для примера максимальное количество рыцарей. Пусть dp[i][mask_prev][mask_cur] — максимальное количество рыцарей, которые могут быть в расстановке из первых i столбцов, mask_cur — маска i-го столбца, а mask_prev — (i – 1)-го.
Затем переберем маску для (i + 1)-го столбца и проверим, выполняются ли ограничения на соседей для солдат из i-го столбца, так как теперь известны все их соседи. Для первого и последнего столбца ограничения нужно проверять отдельно, потому что у них нет одного из соседей.
База: dp[2][mask_prev][mask_cur] равно количеству единиц в mask_prev и mask_cur, если mask_prev может стоять слева от mask_cur.
Переход: dp[i + 1][mask_cur][mask_next] = dp[i][mask_prev][mask_cur] + ones(mask_next), где ones(x) — количество единиц в маске x.
Ответ будет максимумом среди всех dp[k][mask_prev][mask_cur], таких, что mask_cur может находиться справа от mask_prev. Наконец, заметим, что случай k = 1 стоит разобрать отдельно, поскольку в этом случае нет предыдущего столбца.
E. Параллелепипед
Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Чёрный рейнджер хочет составить прямоугольный параллелепипед. Для этого он планирует использовать 6 из n прямоугольных листов металла, i-й лист имеет размер ai на bi метров.
Каждая грань параллелепипеда должна представлять собой цельный лист металла. Листы нельзя гнуть или разрезать, листы, из которых будет сложен параллелепипед, не должны выступать за его края. Листы можно поворачивать произвольным образом.
Чёрный рейнджер хочет построить параллелепипед максимального объёма. Помогите ему.
Входные данные
В первой строке дано одно число n — количество листов металла у чёрного рейнджера (6 ≤ n ≤ 200 000).
В следующих n строках даны пары чисел ai, bi — размеры i-го листа металла (1 ≤ ai, bi ≤ 106).
Выходные данные
Выведите одно целое число — максимальный объём прямоугольного параллелепипеда, который можно собрать из этих листов металла.
Если из данных листов невозможно собрать прямоугольный параллелепипед, выведите –1.
Расскажем об основной идее решения. Во-первых, рассмотрим отдельно все параллелепипеды, у которых две или три стороны совпадают, это можно сделать за O(n).
Пусть теперь все три стороны различны. Построим следующий неориентированный граф: вершинами будут возможные длины сторон, соединим ребром числа a и b, если имеются хотя бы два листа размером a × b. Задача свелась к рассмотрению треугольников в получившемся графе, это можно сделать за O(n2 / w) или O(nsqrt(n)) (здесь w обозначает размер машинного слова, 32 или 64, этот множитель возникает при битовом сжатии в поиске треугольников).
Что дальше?
Приглашаем вас на квалификационные раунды! Они состоятся 2, 16 и 29 апреля. Лучшие 200 программистов каждого раунда пройдут в отборочный раунд. Они получат специальные сертификаты и поборются за памятный приз — крутую футболку с логотипом чемпионата. А 50 лучших программистов отборочного раунда попадут в финал, где разыграют между собой призовой фонд в 750 тысяч рублей. Присоединяйтесь!
Автор: Mail.Ru Group
