Russian Code Cup 2013: разбор задач первого квалификационного раунда

Идея: Виталий Аксёнов
Реализация: Виталий Аксёнов
Разбор: Виталий Аксёнов
Подробная постановка задачи
Ограничение по времени — 1 секунда
Ограничение по памяти — 256 мегабайт
Сейчас в Гномляндии ведется подготовка к предстоящей олимпиаде. Гному-бригадиру было поставлено задание — построить поля для игры в хёртбол, джорданбол и медвебол. Каждое поле представляет собой прямоугольник. В соответствии с правилами игр поля должны быть расположены таким образом, чтобы их стороны были параллельны направлениям север-юг и запад-восток.
Земля в Гномляндии очень дорогая, поэтому организаторы игр хотят потратить на выкуп земли как можно меньше денег. Поскольку соревнования по хёртболу, джорданболу и медвеболу будут проводиться в разное время, поля могут перекрываться.
Помогите гномам найти минимальную площадь, которую могут занимать три поля после постройки.
Одно из возможных оптимальных расположений полей в первом примере приведено на рисунке.

Формат входных данных
Входные данные содержат не более 1000 строк, каждая из которых содержит в себе описание трёх полей — шесть натуральных чисел, каждое из которых не превосходит 10000.
Первое и второе число обозначают размеры первого поля, третье и четвёртое — размеры второго поля, пятое и шестое — размеры третьего поля.
Ввод заканчивается строкой, состоящей из шести нулей. Этот запрос обрабатывать не нужно.
Формат выходных данных
Для каждого набора выведите число — минимальную площадь, которую могут занимать три поля.
Для того чтобы решить задачу, можно заметить, что существует оптимальное решение, в котором у всех трёх данных прямоугольников один из углов общий.
Выполним перебор того, как положить каждое поле — вертикально или горизонтально. После того, как мы зафиксировали положение полей, достаточно просто посчитать площадь объединения прямоугольников. Ее можно посчитать следующим образом: S = S₁ + S₃ + S₃ — S₁₂ — S₂₃ — S₁₃ + S₁₂₃, где S_i — площадь i-го прямоугольника, S_ij — площадь пересечения двух прямоугольников с номерами i и j, а S₁₂₃ — площадь пересечения всех трех прямоугольников.

Идея: Виталий Демьянюк
Реализация: Виталий Демьянюк
Разбор: Виталий Демьянюк
Подробная постановка задачи
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
Однажды Антон Сергеевич рассказывал студентам алгоритм построения трапецоидных карт. В качестве разминки он дал им задачу о трапециях. Он нарисовал на доске n отрезков. Длина i-го отрезка равна ai. Студентам требуется найти количество различных наборов из четырех отрезков, из которых можно составить равнобедренную трапецию ненулевой площади.
Напомним, что равнобедренная трапеция — это четырехугольник, две противоположных стороны которого параллельны, а две других — равны. Пример равнобедренной трапеции приведен на рисунке.

Два набора считаются различными, если существует отрезок, принадлежащий первому набору и не принадлежащий второму. Номера взятых отрезков в каждом наборе должны быть попарно различными.
Помогите студентам найти количество таких наборов.
Формат входных данных
В первой строке задано число t — столько раз Антон давал своим студентам эту задачу. В следующих 2t cтроках содержится описания всех задач.
Описание каждой задачи состоит из двух строк. В первой строке описания дано число n — количество отрезков, нарисованных на доске. Во второй строке описания задачи дано n целых чисел ai — их длины (4 ≤ n ≤ 5000, 1 ≤ ai ≤ 108 для всех i от 1 до n).
Суммарное число всех отрезков во всех задачах не превышает 5000.
Формат выходных данных
Для каждой задачи в отдельной строке выведите одно число — искомое количество наборов.
Обозначим длины меньшей и большей параллельных сторон трапеции за a и b соответственно, а за c — длину боковых сторон. Тогда трапецию можно составить только в том случае, когда a + 2c > b. Перебрав a, b и с, получаем решение за O(n³).
Заметим, что при фиксированном b и возрастающем c уменьшается минимально возможное a. Будем перебирать b в порядке увеличения и, при фиксированном b, будем перебирать c также в порядке увеличения. При переборе c будем поддерживать указатель на минимально возможное a. Зная b, c, минимально возможное a, и использовав простые комбинаторные формулы, несложно вычислить количество наборов из четырех отрезков, образующих трапецию с заданными параметрами.
Также нужно не забыть обработать случаи, в которых a = b, a = c, b = c, и аккуратно следить за тем, чтобы в каждой четверке номера отрезков были попарно различными. Итоговая сложность равна O(n²).

Идея: Виталий Аксенов
Реализация: Павел Кротков
Разбор: Павел Кротков
Подробная постановка задачи
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
Открытый в 2345 году химический элемент млуран очень радиоактивен. Неправильное обращение с млураном может привести к непредсказуемым последствиям, поэтому при его использовании, хранении и транспортировке необходимо соблюдать особую осторожность.
Существует много различных изотопов млурана, каждый из которых характеризуется одним натуральным числом — своей атомной массой. При длительном хранении вместе любой пары изотопов, сумма масс которых равна одному из k «критических чисел», эта пара изотопов вступает в реакцию и происходит взрыв. Известно, что все критические числа являются неотрицательными степенями двойки.
В ядерной лаборатории Флатландии образцы млурана хранятся на двух специальных складах. Ученым удалось получить n различных изотопов млурана, массы которых являются числами от 1 до n. Теперь необходимо распределить изотопы по складам для хранения. Безопасными называются такие способы хранения, при которых каждый изотоп хранится ровно на одном складе, а любые два различных изотопа, сумма масс которых равна одному из «критических чисел», хранятся на разных складах.
Помогите ученым выяснить, сколько существует различных безопасных способов хранения млурана.
Формат входных данных
Входные данные к задаче содержат несколько тестовых наборов. Описание каждого набора состоит из двух строк.
Первая строка описания содержит два целых числа n и k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 61) — количество изотопов, которые необходимо хранить, и количество «критических чисел». Следующая строка содержит k различных натуральных чисел, каждое из которых является степенью двойки и не превышает 2n — критические числа. Критические числа отделены друг от друга пробелами.
Количество наборов данных в каждом тесте не превышает 10000. Последняя строка теста содержит два нуля.
Формат выходных данных
Для каждого тестового набора на отдельной строке выведите количество безопасных способов хранения всех изотопов на двух складах, взятое по модулю 109 + 7.
Реализуем сначала решение, работающее за линейное время. Будем рассматривать массы изотопов в порядке возрастания, начав с 1. Пусть k — текущее число, а 2^t — минимальная степень двойки, большая k. В таком случае:

• если k является степенью двойки или 2^t не лежит в множестве «критических чисел», изотоп массы k можно хранить на любом складе
• в противном случае изотоп массы k можно хранить только на том складе, на котором нет изотопа массы 2^t — k

Заметим, что ответ равен 2^{x + d}, где d — количество степеней двойки, не меньших 1 и не больших n, а x — количество таких чисел, не являющихся степенями двойки, что минимальная большая их степень двойки не лежит в множестве «критических чисел». Значит, можно разбить все числа от 1 до n на log₂n отрезков, границы которых — соседние степени двойки, после чего выбрать нужные отрезки и просуммировать их длины.

Идея: Виталий Аксёнов
Реализация: Николай Ведерников
Разбор: Николай Ведерников
Подробная постановка задачи
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
После недавнего падения метеорита на Урале правительства многих стран задумались о защите Земли от астероидов. Для этого было создано Международное Антиметеоритное Агентство (МАМА), в которое были приглашены лучшие учёные в области астрофизики.
За несколько недель учёные выяснили, что в непосредственной близости от Земли летают n астероидов, при этом если астероид находится от Земли на расстоянии строго больше, чем R, то он не представляет для неё опасности. Для простоты учёные предположили, что все астероиды поблизости от Земли летают по прямой, и определили их положение и вектор скорости в нулевой момент времени. Теперь учёные хотят научиться отвечать на запросы сколько астероидов представляют для Земли опасность в некоторый момент времени.
Для удобства введём прямоугольную декартову систему координат. Пусть Земля имеет координаты (0, 0, 0). Все астероиды и Земля считаются материальными точками в пространстве.
Задано несколько запросов об определенных моментах времени. Для каждого из них требуется определить, сколько астероидов в этот момент представляют опасность для Земли.
Формат входных данных
Первая строка содержит два целых числа n и R (1 ≤ n ≤ 100000, 1 ≤ R ≤ 106) — количество астероидов и радиус зоны опасности.
В каждой из следующих n строк содержится по шесть целых чисел xi, yi, zi, vxi, vyi и vzi (−106 ≤ xi, yi, zi ≤ 106, −100 ≤ vxi, vyi, vzi ≤ 100) — координаты, задающие начальное положение и вектор скорости i-го астероида. Гарантируется, что вектор скорости не равен 0.
В следующей строке содержится одно целое m (1 ≤ m ≤ 100000) — количество моментов времени, которые интересуют учёных.
В каждой из следующих m строк содержится по одному целому числу ti (0 ≤ ti ≤ 107) — момент времени, интересующий ученых.
Формат выходных данных
Для каждого момента времени выведите единственное целое число — количество астероидов, которые находятся в опасной зоне.
Рассмотрим каждый метеорит и найдём времена входа и выхода в зону опасности. Для этого в уравнение сферы x²+y²+z²= R² подставим уравнение прямой, задающей траекторию движение метеорита, то есть x = x₀+dx•t, y = y₀+dy•t, z = z₀+dz•t. У нас получится квадратное уравнение относительно времени. Корни и будут являться интересующими нас временами. В этой задаче могли возникнуть проблемы с точностью чисел с плавающей точкой, поэтому, если корень уравнения был достаточно близок к целому числу, его необходимо было округлить.
Добавим эти времена к запросам и отсортируем по возрастанию. Если время совпадает, то сначала пойдут те времена, которые соответствуют времени входа, затем запросы, а в конце — времена выхода из зоны опасности. Заведем счетчик, который считает, сколько у нас метеоритов в опасной зоне. Если текущее время — время входа, то увеличиваем его; если это запрос, то записываем ответ на этот запрос, в ином случае уменьшаем ответ.
Время работы O((n + m)•log(n + m))

Идея: Анна Малова
Реализация: Борис Минаев
Разбор: Борис Минаев
Подробная постановка задачи
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
2112 год подходил к концу, и вы вместе с небольшой командной единомышленников решили отправиться на поиски сокровищ в одну заброшенную страну. Города этой страны соединены дорогами, по которым можно передвигаться в обоих направлениях. Вам известно, что жители этой страны любили закапывать свои сокровища вдоль этих дорог. Поэтому вы хотите проехать по всем дорогам этой страны и найти закопанные сокровища. Вам необходимо заранее составить эффективный план путешествия. Для этого следует выбрать некоторый город, с которого следует начать свое путешествие. Далее, перемещаясь по дорогам, посетить еще некоторые города. Составленный план называется эффективным, если каждая дорога будет посещена вами ровно один раз.
Составление плана осложняется одним фактом. Некоторые пары городов соединены телепортами. Например, если город A и город B соединены телепортом, то, приехав по некоторой дороге в город A, вы сразу же телепортируетесь в город B и можете продолжить движение только по дорогам, которые соединены с городом B. Аналогично, если вы приехали по дороге в город B, то сразу же телепортируетесь в город А и продолжаете движение по дорогам, которые соединены с городом A.
Каждый город может быть соединен телепортом не более чем с одним другим городом. Вам необходимо составить эффективный план путешествия.
Формат входных данных
Входные данные содержат описание нескольких тестов. Каждый тест имеет следующую структуру. В первой строке содержатся три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 0 ≤ k ≤ 105) — количество городов, количество дорог и количество телепортов. В следующих m строках содержатся по два различных числа — номера городов, которые соединяет очередная дорога. Далее в k строках содержатся по два различных числа, описывающие пары городов, которые соединены телепортами.
Между двумя городами может быть несколько дорог. Никакой город не соединен дорогой сам с собой. Никакой город не соединен телепортом сам с собой. Любой город соединен телепортом не более чем с одним другим городом.
Гарантируется, что суммарное количество городов во всех тестах не превышает 105. Аналогично, суммарное количество дорог и суммарное количество телепортов также не превышает 105. Последняя строка входных данных содержит три нуля. Их обрабатывать не нужно.
Формат выходных данных
Для каждого набора данных выведите ответ в следующем формате: если эффективный план посещения составить нельзя, в единственной строке выведите No. Иначе в первой строке выведите Yes, а во второй — m чисел, обозначающие номера дорог. Дороги следует выводить в том порядке, в котором их надо посетить. Дороги нумеруются с единицы в том порядке, в котором они даны во входных данных. Для каждого теста дороги нумеруются независимо.
Для удобства обозначим количество дорог, которые ведут в город i, как с_i. Для начала нам необходимо определить, существует ли вообще эффективный план путешествия. Во-первых, если есть два города i и j такие, что с_i ≠ 0 и с_j ≠ 0 и не существует пути между i и j, то план мы построить не можем. Следует заметить, что путь может содержать не только дороги, но и телепорты.
Пусть мы уже построили некоторый путь, который проходит через все дороги. Понятно, что для всех городов, которые не соединены телепортами не являются первым или последним городом на пути, сi должно быть четным. Если же два города i и j соединены телепортом и ни один из них не является ни первым, ни последним городом на пути, то с_i должно быть равно с_j.
Рассмотрим, что же происходит с городами, которые лежат на концах пути. Во-первых, если город i соединен телепортом с j и лежит на конце пути, то с_i= с_j + 1 (кроме случая, когда j также является концом пути). При этом если путь начинается и заканчивается в городе i, то с_i = с_j + 2. Если же город не соединен телепортом с другим и находится на одном из концов пути, то его с_i может быть нечетным.
В итоге, чтобы проверить существование пути, необходимо сделать следующее. Посчитаем для каждого города некоторую величину a_i. Если город i соединен с j телепортом, то a_i = max(0, c_i — c_j). В противном случае, a_i = с_i mod 2. Если сумма всех a_i равна двум или нулю, то путь существует, иначе нет.
Построение плана посещения страны аналогично построению Эйлерового пути в обычном графе. Начинать поиск необходимо с вершины, у которой a_i ≠ 0; если же такой нет, то с любой, у которой с_i ≠ 0. При переходе к очередной вершине, если она соединена с другой вершиной телепортом, необходимо просто перейти к ней и продолжить поиск пути дальше. Доказательство того, что путь действительно найдется полностью, аналогично доказательству существования Эйлерового пути в обычном графе.
Итоговая сложность равна O(n + m + k).