Russian Code Cup 2013 – разбор задач 2-го квалификационного раунда

Вот и прошел второй квалификационный раунд. Майские праздники, многие разъехались кто куда. Однако для того, чтобы пройти в отборочный тур, участникам 2-го квалификационного раунда пришлось побороться.
Как и в предыдущем раунде, зарегистрировалось большее число людей, чем прислали решения. Поэтому в числе принявших участие мы отражаем только тех, кто прислал хотя бы одно решение и таким образом может считаться действительно принявшим участие.
Майская жара и 5 задач, которые требуется решить за 2 часа.
Темы задач были такие:

• Задача A. Молекула.
• Задача B. Морской бой.
• Задача C. Пробка.
• Задача D. Таблица.
• Задача E. Космическая экспедиция.

Немного статистики по итогам 2-й квалификации.
Авторизовалось за время раунда 735 человек. Из них хотя бы одно решение прислал 536 человек.
Всего решений было отправлено 2707.
Вот никнеймы участников, которые первыми прислали правильное решение задач:

• Задача А: Rayblast (время после начала раунда (мин: сек) 2:56)
• Задача B: Milanin (время после начала раунда (мин: сек) 2:56)
• Задача C: KAN (время после начала раунда (мин: сек) 2:56)
• Задача D: XopEka (время после начала раунда (мин: сек) 2:56)
• Задача E: maria.sharapova (время после начала раунда (мин: сек) 2:56)

Территориальное распределение участников в этом раунде было следующим:
Россия => 343
Украина => 78
Беларусь => 29
Соединенные Штаты Америки => 22
Казахстан => 16
Армения => 8
Польша => 5
Азербайджан => 4
Узбекистан => 4
Ирландия => 3
Грузия => 3
Кыргызстан => 3
Швеция => 2
Великобритания => 2
Германия => 2
Молдова => 2
Исландия => 1
Бельгия => 1
Пакистан => 1
Латвия => 1
Республика Корея => 1
Испания => 1
Китай => 1
Чехия => 1
Швейцария => 1
Канада => 1
В отборочный тур, как и в предыдущем раунде, вышел 201 человек.

1. Михаил Колупаев
2. Евгений Соболев
3. Андрей Гриненко
4. Евгений Капун
5. Денис Дублённых
6. Алексей Сафронов
7. Владислав Симоненко
8. Андрій Павлисько
9. Егор Суворов
10. Павел Маврин

А теперь рассмотрим разбор задач. Данный разбор доступен также на сайте Russian Code Cup.
Напомним, что остался последний, 3-й квалификационный раунд. Если вы хотите принять участие в финале, то поспешите пройти последнюю квалификацию, чтобы иметь возможность сразиться в отборочном туре.

Задача A. Молекула.
Идея: Виталий Аксенов.
Условие: Анна Малова.
Реализация: Андрей Комаров.
Разбор: Анна Малова.

Условие задачи
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
В результате последних исследований в сверхсекретной лаборатории было открыто новое вещество. Каждая молекула этого вещества представляет цикл, состоящий из двух видов атомов, которые мы будем условно называть черными и белыми (настоящие названия атомов держатся в строгом секрете). Для проведения сверхсекретной реакции необходимо перевести молекулу в нестабильное состояние, в котором она может распасться на две независимые молекулы, каждая из которых состоит только из одного вида атомов.
Исследования показали, что молекула распадается, если все атомы каждого цвета образуют непрерывный блок.
Для перестроения молекулы ученые могут осуществлять следующую операцию: непрерывная последовательность атомов вырезается из цикла и вставляется в другое место. Пример перестроения молекулы приведен на рисунке.

Теперь ученые пытаются выяснить, за какое минимальное число описанных операций можно привести молекулу в нестабильное состояние. Помогите им это выяснить.Теперь ученые пытаются выяснить, за какое минимальное число описанных операций можно привести молекулу в нестабильное состояние. Помогите им это выяснить.

Формат входных данных	В первой строке входного файла содержится натуральное число n — число молекул, которые необходимо исследовать. В каждой из следующих n строк содержится описание одной молекулы в следующем формате: строка, состоящая не менее чем из трех букв w и b, обозначающих белый и черный атомы, соответственно. Гарантируется, что каждая буква встречается в каждой молекуле хотя бы один раз. Суммарная длина всех молекул не превышает 200000. Выведите n строк. В i-ой строке выведите минимальное число операций, которое необходимо выполнить, чтобы i-я молекула перешла в нестабильное состояние.В первой строке входного файла содержится натуральное число n — число молекул, которые необходимо исследовать. В каждой из следующих n строк содержится описание одной молекулы в следующем формате: строка, состоящая не менее чем из трех букв w и b, обозначающих белый и черный атомы, соответственно. Гарантируется, что каждая буква встречается в каждой молекуле хотя бы один раз. Суммарная длина всех молекул не превышает 200000.
Формат выходных данных	Выведите n строк. В i-ой строке выведите минимальное число операций, которое необходимо выполнить, чтобы i-я молекула перешла в нестабильное состояние.
Примеры	Входные данные Выходные данные 3 wbbw wbbwb wbwbwb 0 1 2

Разбор
Обозначим за m число блоков одинакового цвета в молекуле. Заметим, что m четное, а число черных и белых блоков одинаково. Из очевидного факта, что у куска два конца и он задевает два блока следует, что при каждой перестройке молекулы, число блоков каждого цвета уменьшится не более, чем на один. Уменьшить число блоков каждого цвета ровно на один можно следующим образом: вырежем один блок и встроим его в середину другого блока такого же цвета. Таким образом, всего ученым потребуется m/2 — 1 операций.
Время работы O (длины молекулы).

Задача B. Морской бой.
Идея: Виталий Аксёнов.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

Условие задачи
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Петя и Вася играют в морской бой с немного модифицированными правилами. Вася проиграл уже десять игр подряд и не намерен потерпеть поражение снова. Он проанализировал тактику боя Пети и нашел в ней существенный недостаток (по крайней мере, он очень сильно на это надеется). Оказалось, что на поле есть прямоугольник размера A на B клеток, в который Петя за все десять игр ни разу не стрелял. Поэтому Вася решил взять три своих самых больших корабля и разместить в этом прямоугольнике.
Планы Васи, конечно, далеко идущие, но ему все же необходимо вначале справиться с некоторыми мелкими проблемами. Например, ему необходимо узнать, сможет ли все-таки он расставить три своих корабля так, чтобы они полностью помещались в заданный прямоугольник. По правилам, корабли являются прямоугольниками, которые требуется располагать параллельно сторонам поля. Корабли разрешается поворачивать на 90 градусов. Корабли могут касаться друг друга, но они не должны иметь общих клеток поля.

Формат входных данных	В первой строке содержится целое число t (1 ≤ t ≤ 105) — количество тестов. Описание каждого теста состоит из 4 строк. В первой из них находятся два целых числа A и B (1 ≤ A, B ≤ 109 ) — размеры прямоугольника, в котором необходимо разместить корабли. В следующих трех строках содержаться по два целых числа ai и bi (1 ≤ ai, bi ≤ 109) — размеры i-го корабля.
Формат выходных данных	Вам необходимо вывести t строк, которые являются ответами на тесты из входных данных. Для каждого теста выведите Yes, если корабли разместить можно и No в противном случае.
Примеры	Входные данные Выходные данные 2 7 7 6 3 6 1 3 3 4 4 5 1 1 1 1 2 Yes No

Разбор

Отметим следующий факт. Пусть мы нашли расстановку прямоугольников, которая удовлетворяет условию. Тогда существует линия, параллельная какой-то стороне большого прямоугольника, такая, что один из маленьких прямоугольников окажется полностью с одной стороны от нее, а два других — с другой. Оставим доказательство этого факта в качестве упражнения.
Воспользуемся этим фактом. Переберем все возможные повороты прямоугольников (в том числе и большого) — их всего 16. Если существует правильная расстановка, то существует и горизонтальная линия (хотя бы для одного варианта поворотов), которая разделяет прямоугольники. Переберем прямоугольник, который окажется ниже этой линии и разобьем большой прямоугольник горизонтальной линией на две части. Осталось проверить, что выбранный прямоугольник поместится по ширине в большой, а два других можно разместить в верхней части.
Если хотя бы в одном из случаев мы смогли разместить прямоугольники, то ответ Yes, иначе No.

Задача C. Пробка.
Идея: Виталий Аксенов.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

Условие задачи
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
В 2050 году с целью повышения безопасности дорожного движения на всех дорогах были запрещены обгоны. Более того, запрещается приближаться к впереди идущей машине ближе чем на L метров, за соблюдением правил следят расставленные на всех дорогах видеокамеры. К сожалению, эти меры не в полной мере помогли в борьбе с пробками.
Профессор Свинкин каждое утро добирается из дома на работу. Дорога, по которой он едет, представляет собой прямую, введем на ней систему координат с единицей равной метру и будем представлять машины отрезками на этой прямой, которые двигаются в сторону увеличения координаты.
Исходно машина профессора расположена в начале дороги, так что ее передняя точка находится в начале координат. Максимальная скорость машины профессора равна V метров в секунду.
Кроме машины профессора на дороге есть еще n машин, которые двигаются по дороге. При движении каждая машина старается двигаться со своей максимальной скоростью. Когда машина A догоняет впереди идущую машину B, так что передняя точка A оказывается на расстоянии ровно L от задней точки B, машина A мгновенно снижает свою скорость до скорости B и в дальнейшем повторяет все изменения скорости B. Ни одна машина не покидает дорогу.
Найдите время, за которое профессор Свинкин доберется до своей работы. Считается, что это произошло, если передняя точка его машины оказалась в точке с координатой S.

Формат входных данных	Входные данные к задаче содержат несколько тестовых наборов. Описание каждого набора состоит из нескольких строк. Первая строка описания содержит четыре целых числа n, L, S и V(1 ≤ n ≤ 10000, 1 ≤ L ≤ 1000, 1 ≤ S ≤ 109, 1 ≤ V ≤ 100) — количество машин перед профессором, минимальное расстояние между машинами в метрах, расстояние от дома до места работы профессора и максимальная скорость машины профессора в метрах в секунду. В следующих n строка содержатся по три целых числа xi, li и vi (1 ≤ xi ≤ 109, 1 ≤ li ≤ 10, 1 ≤ vi ≤ 100) — координата передней точки i-й машины в начальный момент времени, ее длина и максимальная скорость в метрах в секунду. Гарантируется, что машины заданы в порядке удаления он машины профессора, и что расстояние между двумя соседними машинами в начальный момент не меньше, чем L метров. Последняя строка теста содержит четыре нуля. Суммарное количество машин во всех тестах не привышает 10000.
Формат выходных данных	Для каждого тестового запроса выведите в отдельной строке время, за которое профессор доедет на работу, в секундах. Ответ должен быть выведен с абсолютной или относительной погрешностью не более чем 10−5.Для каждого тестового запроса выведите в отдельной строке время, за которое профессор доедет на работу, в секундах. Ответ должен быть выведен с абсолютной или относительной погрешностью не более чем 10−5.
Примеры	Входные данные Выходные данные 1 1 10 2 3 1 1 1 1 10 1 3 2 1 1 1 10 2 3 1 2 2 3 15 3 4 1 2 10 3 1 1 3 500 93 123 3 2 0 0 0 0 9.0000000000 10.0000000000 5.0000000000 15.0000000000 191.5000000000

Разбор
В задаче требовалось узнать, за сколько минут профессор доедет до своей работы. Когда одна машина догоняет другую, она начинает ехать за ней с той же скоростью. Тогда можно считать, что первая машина имеет длину len_first + L + len_second, а второй нет. Рассмотрим момент времени, когда i-ая машина догонит (i + 1)-ую, если же она её не догонит, будем считать, что этот момент произойдёт в бесконечности. Так же рассмотрим момент времени, когда машина профессора доедет до финиша. Выберем событие, которое произойдёт раньше всего. Добавим время, через которое оно произойдет, к ответу. Если же это событие — финиш машины профессора, то задача решена. Иначе объединим машины по описанному выше правилу и решим задачу меньшей размерности. Эта фаза выполняется за O(n). Всего таких фаз не более чем n.
Итого время работы O(n2). Применением различных структур данных это решение можно ускорить до O(n log n) и даже до O(n).

Задача D. Таблица.
Идея: Виталий Аксёнов.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

Условие задачи
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Рассмотрим прямоугольную таблицу, составленную из n×m клеток. Каждую клетку разрешается покрасить в черный либо в белый цвет. Раскраска называется правильной, если не существует четырех клеток одинакового цвета, центры которых расположены в углах невырожденного прямоугольника со сторонами, параллельными сторонам таблицы.
Требуется посчитать число различных правильных раскрасок прямоугольника. Так как это число может быть большим, необходимо вывести его по заданному модулю r.
Например, для прямоугольника 2×2 число таких раскрасок равно 14: подходят все раскраски, кроме тех, у которых все четыре клетки покрашены в один цвет.

Формат входных данных	В первой строке входного файла содержится натуральное число t — количество тестов (1 ≤ t ≤ 150). В каждой из следующих t строк содержится 3 целых числа: n, m и r — размеры таблицы и модуль, по которому требуется вывести ответ. (1 ≤ n, m, r ≤ 1018)
Формат выходных данных	Для каждого тестового запроса выведите ответ в отдельной строке.
Примеры	Входные данные Выходные данные 2 1 1 2 2 2 1000000 0 14

Разбор
Будем обозначать минимальную сторону прямоугольника за n, а максимальную за m. Расположим таблицу длинной стороной горизонтально и, соответственно, будем называть более короткие ряды столбцами.
Следует разобрать 3 случая:
• n= 1. Тогда ответ будет равен 2^m.
• n = 2. Мы можем себе позволить только два одноцветных столбца — один чёрного, а другой белого цвета. Все остальные столбцы должны быть двухцветные, то есть у каждого по два варианта. Значит, ответ равен C_m²•2^{m — 1} + C_m¹ •2^m + 2^m.
• n > 2. Можно заметить, что если m > 6, то не существует ни одной хорошей раскраски. Действительно, раскраска первого столбца с раскраской второго может совпадать только в двух местах. Аналогично, с раскрасками первого и третьего. А если m > 6, то раскраска второго и третьего совпадают как минимум в трёх местах. А это и означает, что хорошей раскраски нет. После того, как мы ограничили размеры таблицы, легко понять, что для оставшихся успевает отработать перебор.
В этой задаче ещё была одна небольшая трудность — перемножение чисел по большому модулю. Чтобы решить эту проблему, можно использовать бинарный алгоритм умножения по модулю, аналогичный соответствующему алгоритму возведения в степень.

Задача E. Космическая экспедиция.
Идея: Виталий Аксенов.
Реализация: Павел Кротков.
Разбор: Павел Кротков.

Условие задачи
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
В 2345 году у человечества появилась возможность отправить первую космическую экспедицию к далекой планете Нутпен. Путь до нее долог и полон опасностей, поэтому было решено отправить к ней сразу nкосмических кораблей разных типов.
Каждый корабль может работать на одном из двух различных типов топлива. Поскольку корабли разные, их расход топлива тоже может различаться. При этом в полете корабль должен использовать только один из двух типов топлива, переходить с одного на другой в космосе нельзя.
Про корабль номер i известно, что на дорогу до планеты Нутпен он потратит или ai килотонн топлива первого типа, или bi килотонн топлива второго типа. В силу конструктивных особенностей кораблей, для любого из них выполняется равенство ai + bi = 4k, причем число k одинаково для всех кораблей.
В распоряжении командования экспедиции есть ровно k(n + 1) килотонн топлива первого типа и столько же килотонн топлива второго типа. Теперь вам необходимо решить, на каком типе топлива каждый из кораблей полетит к планете Нутпен.

Формат входных данных	Первая строка содержит одно целое число t — количество наборов входных данных в тесте. Далее следует описание самих наборов входных данных. В первой строке описания очередного набора входных данных содержится целое число n (1 ≤ n ≤ 105) — количество кораблей, которые полетят к планете Нутпен. Следующие n строк содержат по два целых неотрицательных числа ai и bi — количество топлива первого и второго типа, необходимое соответствующему кораблю. Гарантируется, что сумма ai и bi у всех кораблей одинакова, кратна четырем и не превышает 108. Сумма n во всех наборах в одном тесте не превышает 500000.
Формат выходных данных	Для каждого набора входных данных выведите единственную строку, состоящую из n символов, в которой символ номер i является символом ‘1’, если корабль номер i должен лететь на Нутпен, используя топливо первого типа, и символом ‘2’, если ему необходимо использовать топливо второго типа. Количество необходимого топлива каждого из типов не должно превосходить k(n + 1). Если возможных ответов несколько, выведите любой из них. Гарантируется, что ответ всегда существует.
Примеры	Входные данные Выходные данные 2 5 1 3 3 1 2 2 4 0 0 4 1 4 4 12221 2

Разбор
Отсортируем все корабли по количеству топлива первого типа, которое им необходимо. После чего выберем максимальное t такое, что сумма ai у первых t кораблей не превышает k(n + 1). Эти t кораблей будут использовать топливо первого типа, а все остальные — топливо второго типа.
Докажем, что этот алгоритм всегда найдет ответ при условиях, поставленных в задаче. Заметим, что сумма ∑_i=1^t+1a_i > n • (k+1). Значит, что для любого i > t выполняется a_i > (n+1)/(t+1). Следовательно, получаем, что для любого i > t выполнено b_i < 4k — (n+1)/(t+1). Осталось доказать, что вторая сумма не превышает заявленного выражения. ∑_i=t+1ⁿ b_i < (n — (t+1) + 1) • (4k — (n+1)/(t+1)) ≤ (n+1) k. Последнее неравенство, после раскрытия скобок, превращается в неравенство «среднее арифметическое — среднее геометрическое». Значит, приведенный алгоритм всегда найдет решение.