Вот и прошел второй квалификационный раунд Russian Code Cup. Майские праздники, многие разъехались кто куда… Однако для того чтобы пройти в отборочный тур, участникам второго квалификационного раунда пришлось побороться.
Как и в предыдущем раунде, зарегистрировавшихся было больше, чем приславших решения. Поэтому в числе принявших участие мы отражаем только тех, кто прислал хотя бы одно решение.
Майская жара и 5 задач, которые требуется решить за 2 часа:
- задача A. Молекула
- задача B. Морской бой
- задача C. Пробка
- задача D. Таблица
- задача E. Космическая экспедиция
Условия и решение — под катом.
Немного статистики по итогам второй квалификации.
Авторизовались за время раунда 735 человек. Из них хотя бы одно решение прислали 536 человек.
Всего было отправлено 2707 решений.
Вот никнеймы участников, которые первыми прислали правильное решение задач (в скобках — время после начала раунда в минутах и секундах)
- Задача А: Rayblast (2:56)
- Задача B: Milanin (14:58)
- Задача C: KAN (20:27)
- Задача D: XopEka (51:58)
- Задача E: maria.sharapova (18:45)
Территориальное распределение участников в этом раунде было таким:
Россия => 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 человек.
- Михаил Колупаев
- Евгений Соболев
- Андрей Гриненко
- Евгений Капун
- Денис Дублённых
- Алексей Сафронов
- Владислав Симоненко
- Андрій Павлисько
- Егор Суворов
- Павел Маврин
А теперь рассмотрим разбор задач (разбор доступен также на сайте Russian Code Cup).
Напомним, что остался последний, 3-й квалификационный раунд. Если вы хотите принять участие в финале, то поспешите пройти последнюю квалификацию, чтобы иметь возможность сразиться в отборочном туре.
Задача A. Молекула
Идея: Виталий Аксенов
Условие: Анна Малова
Реализация: Андрей Комаров
Разбор: Анна Малова
Условие задачи
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
В результате последних исследований в сверхсекретной лаборатории было открыто новое вещество. Каждая молекула этого вещества представляет цикл, состоящий из двух видов атомов, которые мы будем условно называть черными и белыми (настоящие названия атомов держатся в строгом секрете). Для проведения сверхсекретной реакции необходимо перевести молекулу в нестабильное состояние, в котором она может распасться на две независимые молекулы, каждая из которых состоит только из одного вида атомов.
Исследования показали, что молекула распадается, если все атомы каждого цвета образуют непрерывный блок.
Для перестроения молекулы ученые могут осуществлять следующую операцию: непрерывная последовательность атомов вырезается из цикла и вставляется в другое место. Пример перестроения молекулы приведен на рисунке.
Теперь ученые пытаются выяснить, за какое минимальное число описанных операций можно привести молекулу в нестабильное состояние. Помогите им это выяснить.
| Формат входных данных | В первой строке входного файла содержится натуральное число n — число молекул, которые необходимо исследовать. В каждой из следующих n строк содержится описание одной молекулы в следующем формате: строка, состоящая не менее чем из трех букв w и b, обозначающих белый и черный атомы соответственно. Гарантируется, что каждая буква встречается в каждой молекуле хотя бы один раз. Суммарная длина всех молекул не превышает 200000. |
||||
| Формат выходных данных | Выведите n строк. В i-ой строке выведите минимальное число операций, которое необходимо выполнить, чтобы i-я молекула перешла в нестабильное состояние. | ||||
| Примеры |
|
Разбор
Обозначим 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 в противном случае. | ||||
| Примеры |
|
Разбор
Пусть мы нашли расстановку прямоугольников, которая удовлетворяет условию. Тогда существует линия, параллельная какой-то стороне большого прямоугольника, — такая, что один из маленьких прямоугольников окажется полностью по одну сторону от нее, а два других — по другую. Оставим доказательство этого факта в качестве упражнения.
Воспользуемся этим фактом. Переберем все возможные повороты прямоугольников (в том числе и большого) — их всего 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. | ||||
| Примеры |
|
Разбор
В задаче требовалось узнать, за сколько минут профессор доедет до своей работы. Когда одна машина догоняет другую, она начинает ехать за ней с той же скоростью. Тогда можно считать, что первая машина имеет длину lenfirst + L + lensecond, а второй нет. Рассмотрим момент времени, когда 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) |
||||
| Формат выходных данных | Для каждого тестового запроса выведите ответ в отдельной строке. | ||||
| Примеры |
|
Разбор
Будем обозначать минимальную сторону прямоугольника n, а максимальную — m. Расположим таблицу длинной стороной горизонтально и, соответственно, будем называть более короткие ряды столбцами.
Следует разобрать 3 случая:
• n= 1. Тогда ответ будет равен 2m.
• n = 2. Мы можем себе позволить только два одноцветных столбца — один чёрного, а другой белого цвета. Все остальные столбцы должны быть двухцветными, то есть у каждого по два варианта. Значит, ответ равен Cm2•2m — 1 + Cm1 •2m + 2m.
• 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). Если возможных ответов несколько, выведите любой из них. Гарантируется, что ответ всегда существует. | ||||
| Примеры |
|
Разбор
Отсортируем все корабли по количеству топлива первого типа, которое им необходимо. После чего выберем максимальное t — такое, что сумма ai у первых t кораблей не превышает k(n + 1). Эти t кораблей будут использовать топливо первого типа, а все остальные — топливо второго типа.
Докажем, что этот алгоритм всегда найдет ответ при условиях, поставленных в задаче. Заметим, что сумма ∑i=1t+1ai > n • (k+1). Значит, для любого i > t выполняется ai > (n+1)/(t+1). Следовательно, получаем, что для любого i > t выполнено bi < 4k — (n+1)/(t+1). Осталось доказать, что вторая сумма не превышает заявленного выражения. ∑i=t+1n bi < (n — (t+1) + 1) • (4k — (n+1)/(t+1)) ≤ (n+1) k. Последнее неравенство, после раскрытия скобок, превращается в неравенство «среднее арифметическое минус среднее геометрическое». Значит, приведенный алгоритм всегда найдет решение.
Напомним, что остался последний, третий квалификационный раунд. Если вы хотите принять участие в финале, поспешите зарегистрироваться на последнюю квалификацию, чтобы иметь возможность сразиться в отборочном туре.
Автор: Dmitry21
