Разбор задач отборочного раунда RCC 201629.06.2016 19:03

Завершился очередной — отборочный — раунд международного чемпионата программистов Russian Code Cup 2016. И по сложившейся традиции мы предлагаем вам ознакомиться с решениями задач, которые предлагались конкурсантам в последнем раунде. На этот раз задач было шесть, хотя на их решение по-прежнему выделялось два часа. За выход в следующий раунд сражалось 604 человека. RCC впервые проводится в том числе для англоязычных участников. Результат не заставил ждать — русскоговорящим программистам будет составлена серьезная конкуренция. В финал прошло 50 человек и из них 19 человек — не русскоговорящие участники. Среди финалистов представители России, Украины, Беларусии, Литвы, Словакии, Армении, Польши, Швейцарии, Финляндии, Японии, Китая, Южной Кореи.

1. Контрольная работа
2. Многоножка
3. Двоичное дерево
4. Пробирки и реактивы
5. Размен денег
6. Задача F

Задача А. Контрольная работа
Условие

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Скоро Коле предстоит писать важную контрольную, поэтому он решил тщательно подготовиться. Он выяснил, что у контрольной будет n вариантов, i-й из которых состоит из mi заданий, пронумерованных от 1 до mi. Для каждого задания каждого варианта Коля оценил время tij минут, которое займёт у него решение.

Во время контрольной он планирует решать задания строго в том порядке, в котором они расположены в варианте. Сдать работу надо не позже окончания контрольной, которая длится t минут. Конечно, Коля мог бы списать контрольную, но он считает, что это не очень правильно. Поэтому готов списать не более одного задания. На списывание любого задания он потратит t0 минут.

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

Формат входных данных

В первой строке находятся три целых числа n, t и t0 (1 ≤ n ≤ 100, 1 ≤ t ≤ 10 000, 1 ≤ t0 ≤ 100) — количество вариантов, продолжительность контрольной и время, которое Коля потратит на списывание задания.

В следующих n строках находится описание вариантов. Первое число mi (1 ≤ mi ≤ 100) — количество заданий в варианте i. Следующие mi чисел tij (1 ≤ tij ≤ 100) — время, которое Коля потратит на решение j-го задания i-го варианта.

Формат выходных данных

Для каждого варианта выведите на новой строке одно целое число — количество заданий, которые Коля успеет решить, если ему попадётся этот вариант.

Примеры

Входные данные
4 45 5
5 10 10 10 10 10
4 30 10 10 10
3 40 40 5
1 100

Выходные данные
5
4
2
1

Решение

Переберём префикс заданий, которые решит Коля. Найдём время, которое он потратит, если будет сам решать все задания, и максимальное время, которое он потратит на одно задание в таком случае. Понятно, что если он будет списывать, то списывать надо именно самое долгое задание из тех, что он делает. Тогда время, которое Коля потратит, равно S — max (0,  M — t0). Теперь найдём наибольший префикс, у которого это время не превышает t.

Задача B. Многоножка
Условие

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

В детстве у мальчика Фили дома жила многоножка. Всего у многоножки было n ног, некоторые из них правые, а некоторые левые. Каждый день многоножка использовала только некоторые из своих ног, но обязательно хотя бы одну левую и хотя бы одну правую.

Каждый день Филя записывал себе в блокнот два числа — сколько левых и сколько правых ног использовала многоножка в этот день.

Филя хочет по своим записям понять, сколько левых и сколько правых ног было у его многоножки. К сожалению, Филя не идеален и мог допустить в нескольких записях ошибки. Филя считает запись li,  ri корректной, если у многоножки было хотя бы li левых и хотя бы ri правых ног.

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

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 10 000).
Каждый из тестов описывается следующим образом: в первой строке описания теста содержится число n (2 ≤ n ≤ 109) — суммарное количество ног многоножки, а во второй строке число m (1 ≤ m ≤ 105) — количество записей.

В следующих m строках содержатся по два числа li и ri (1 ≤ li,  ri ≤ n) — количество левых и правых ног, используемых многоножкой в i-й день согласно записям Фили, соответственно.

Суммарное количество записей по всем тестам не превосходит 105.

Формат выходных данных

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

Примеры

Входные данные
3
4
3
1 2
1 3
1 4
2
2
2 2
1 2
5
4
1 4
2 3
3 2
4 1

Выходные данные
1 3
1 1
1 4

Решение

Чтобы решить эту задачу, можно отсортировать все записи по количеству левых ног. Дальше будем перебирать количество левых ног по возрастанию. Если левых ног li, то потенциально могут быть верными первые i записей, а все последующие записи точно неверны (за исключением количества ног, равного li).

Теперь нужно узнать, сколько записей из первых i будут верны. Запись c номером j ≤ i верна, если rj ≤ n — li. Нахождение всех таких rj является стандартной задачей и решается, например, деревом отрезков.

Также нужно было обратить внимание, что сумма чисел в ответе должна быть равна n, и корректно обрабатывать случай, где все записи могут быть неверны.

Задача C. Двоичное дерево
Условие

Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Студенту Васе для зачёта по биоинформатике нужно вырастить полное двоичное дерево, все листья которого имеют одинаковое расстояние до корня.

Напомним, что подвешенное дерево — это связный неориентированный граф без циклов, в котором одна из вершин является корнем. Родителем вершины называется её сосед, ближайший к корню, у корня нет родителя. Остальные соседи вершины называются её сыновьями. Вершина, у которой нет сыновей, называется листом. Полное двоичное дерево — это подвешенное дерево, каждая вершина которого, не являющаяся листом, имеет ровно двух сыновей.

К сожалению, во время семестра Вася слишком много времени тратил на олимпиады по программированию и не очень следил за ростом своего дерева. За несколько дней до зачёта Вася понял, что дерево у него выросло, но, возможно, неправильно и у него даже корня нет. Вася может сам выбрать корнем дерева любую его вершину и попытаться получить из него требуемое полное двоичное дерево, добавляя вершины. За один день Вася может добавить к дереву новую вершину, сделав её сыном одной из уже существующих.

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

При выводе количества дней, которые ему необходимы, Вася хочет увидеть лишь остаток от деления этого числа на число 109 + 7. Обратите внимание, что Васе надо минимизировать именно число дней, за которое он сможет завершить формирование дерева, а не остаток от его деления на 109 + 7, остаток необходимо взять непосредственно перед выводом.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t.

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста дано одно целое число n (2 ≤ n ≤ 2 • 105) — количество вершин в дереве. В следующих n — 1 строках описания теста даны пары чисел ui, vi (1 ≤ ui,  vi ≤ n) — номера вершин, соединённых i-м ребром. Гарантируется, что рёбра образуют дерево.

Гарантируется, что сумма чисел n по всем тестам не превосходит 2 • 105.

Формат выходных данных

Выведите ответ для каждого теста на отдельной строке.

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

Иначе выведите два целых числа — номер вершины, которую нужно выбрать корнем, и остаток от деления числа дней, которое потребуется Васе, на 109 + 7. Если есть несколько вершин, позволяющих выполнить задание в минимальный срок, выведите вершину с минимальным номером.

Примеры

Входные данные
3
3
1 3
3 2
4
4 2
3 2
3 1
5
1 2
1 3
1 4
1 5

Выходные данные
3 0
2 3
-1

Решение

Чтобы минимизировать количество дней, которые придётся потратить Васе, нужно минимизировать высоту итогового бинарного дерева — если глубина листа в итоговом дереве равна h, то Вася потратит 2h — 1 — n дней на то, чтобы подвесить необходимое число вершин.

Заметим, что если в дереве есть вершина степени больше 3, то задание выполнить не получится, — в полном бинарном дереве все вершины имеют не больше трёх соседей. Обратим внимание, что корень в ответе имеет ровно двух сыновей.

Таким образом, чтобы решить задачу, нужно перебрать корень — вершину степени не больше 2 — и выбрать корнем такую вершину, что максимальное из расстояний от неё до всех остальных минимально. Это и будет высота итогового дерева.

Задача D. Пробирки и реактивы
Условие

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Сегодня учитель химии дал Пете очень ответственное задание — разлить реактивы по пробиркам. В распоряжение ему предоставили n пробирок и m реактивов. Для каждой пробирки известны mini и maxi — минимальное и максимальное суммарное количество жидкости в миллилитрах, которое может в ней находиться, соответственно, а также номер реактива ci и число pi. Для каждого реактива также известно число vi — сколько миллилитров его есть у Пети. Учитель просит Петю разлить все реактивы так, чтобы в i-й пробирке как минимум pi процентов от всей жидкости, в ней находящейся, занимал реактив ci, а также чтобы в каждой пробирке были удовлетворены ограничения на mini и maxi. Все реактивы должны быть полностью разлиты. Будем считать, что никаких химических реакций и изменений объёма реактивов не происходит.

Помогите Пете выполнить задание учителя или скажите, что, как бы он ни пытался, сделать у него это не получится.

Например, в первом тестовом наборе из примера подойдёт следующий ответ:

• В первую пробирку налить 3 миллилитра первого реактива и 2 миллилитра второго.
• Во вторую пробирку налить 4 миллилитра третьего реактива и 1 миллилитр второго.
• В последнюю пробирку налить 3 миллилитра четвёртого реактива и 1 миллилитр второго.

В этом случае все ограничения на mini и maxi выполняются, а также выполняются ограничения на проценты реактивов в пробирках: в первой пробирке 3/5 = 60% первого реактива, во второй пробирке 4/5 = 80% третьего реактива, а в последней пробирке ¾ = 75% ≥ 70% четвёртого реактива. Также все реактивы полностью разлиты, поэтому все требования, данные учителем, выполнены и ответ верен.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 100).

Каждый из следующих t тестов описывается таким образом: в первой строке описания теста содержатся два числа n, m (1 ≤ n,  m ≤ 105) — количество пробирок и реактивов соответственно.

В i-й из следующих n строк содержится четыре целых числа mini, maxi, ci, pi (1 ≤ mini ≤ maxi ≤ 105, 1 ≤ ci ≤ m, 1 ≤ pi ≤ 100) — минимальное и максимальное суммарное количество миллилитров жидкости, которое можно налить в i-ю пробирку, номер реактива и его минимальный процент содержания в пробирке соответственно.

В последней строке описания теста содержатся m целых чисел vi (1 ≤ vi ≤ 105) — количество миллилитров i-го реактива у Пети.

Гарантируется, что сумма n и сумма m во всех тестах не превосходит 105.

Формат выходных данных

Для каждого теста выведите ответ на него.

Если ответ существует, в первой строке выведите YES, а в i-й из следующих n строк выведите сначала число k — количество различных реактивов в i-й пробирке, а затем k пар положительных чисел id, v — номер реактива и его количество в пробирке. Если существует несколько ответов, разрешается вывести любой.

Если ответа на тест не существует, в единственной строке выведите NO.

Ответ будет считаться верным, если будут выполнены все условия, упомянутые в задаче, а также относительная или абсолютная погрешность не будет превышать 10–6.

Примеры

Входные данные
2
3 4
5 8 1 60
4 6 3 80
3 4 4 70
3 4 4 3
3 4
6 8 1 60
4 6 3 80
3 4 4 70
3 4 4 3

Выходные данные
YES
2 1 3.0000000000 2 2.0000000000
2 2 1.0000000000 3 4.0000000000
2 2 1.0000000000 4 3.0000000000
NO

Решение

Приведём конструктивный алгоритм в несколько этапов:

• Если sum (mini) > sum (vi) — ответ NO.
• Если sum (maxi) < sum(vi) — ответ NO.
• Нальём в каждую пробирку mini • pi / 100 миллилитров реактива ci.
• После этого для каждого реактива i отсортируем пробирки, для которых cj = i, по возрастанию pj и будем по очереди наливать в них оставшийся реактив номер i.
• В каждую пробирку нальём ещё (maxj — minj) pj / 100 миллилитров i-го реактива или меньше, если он закончится.
• Всё оставшееся от реактивов разольём по пробиркам любым способом: в i-ю пробирку суммарно можно налить любое количество жидкости, не превосходящее summaryi • 100 / pi (summaryi — суммарное количество жидкости в ней на текущий момент).
• Если разлить не получилось и жидкость осталась — ответ NO.
• Единственная оставшаяся проблема — в каких-то пробирках всё ещё может быть меньше mini миллилитров жидкости.
• Для исправления этого в пробирке i сначала перельём из всех остальных пробирок j реактивы, отличные от cj, в i-ю пробирку, так, чтобы в j-й пробирке осталось хотя бы minj жидкости.
• Если и этого не хватило, перельём из остальных пробирок j жидкость номер cj (теперь это не испортит условие на процентное содержание).

После этих действий получившееся разделение реактивов на пробирки всегда будет удовлетворять всем условиям задачи.
Напоследок отметим, что в этой задаче могли быть определённые проблемы с точностью. Тесты жюри были построены в этом смысле довольно гуманно, но после тура Пётр Митричев (которого мы поздравляем с победой в отборочном раунде) показал тест, в котором происходят существенные потери точности. Мы постараемся в дальнейшем избегать тонкостей с точностью в задачах с вещественными числами.Задача E. Размен денег
Условие

Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

За свою долгую жизнь Боря собрал коллекцию из n монет. Он выложил все эти монеты в ряд. При этом i-я в ряду монета имеет номинал ai.

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

Боря хочет ответить на несколько запросов. В каждом запросе Боря хочет узнать, какую минимальную сумму он не сможет заплатить без сдачи, если он возьмёт все монеты с li-й по ri-ю. Более формально — он хочет найти такое минимальное натуральное число z, что нельзя выбрать подмножество монет с номерами от li до ri, суммарный номинал которых равен z.

Формат входных данных

В первой строке задано два целых числа n и m (1 ≤ n,  m ≤ 150 000) — количество монет у Бори и количество запросов. В следующей строке задано n чисел ai (1 ≤ ai ≤ 109) — номинал i-й монеты.

В следующих m строках задано по два числа li и ri (1 ≤ li ≤ ri ≤ n) — описание запросов.

Формат выходных данных

На каждый из m запросов выведите минимальную сумму, которую нельзя заплатить без сдачи, воспользовавшись монетами с li-й по ri-ю.

Примеры

Входные данные
5 5
2 1 5 3 1
1 5
1 3
1 1
2 4
2 5

Выходные данные
13
4
1
2
11

Решение

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

Пусть на очередном шаге мы рассмотрели все монеты, стоимость которых не превышает X, и мы можем заплатить любую сумму до Y включительно. Пусть суммарная стоимость монет, каждая из которых стоит больше X, но не больше Y + 1, равна sum. Тогда если sum = 0, то Y  + 1 мы не сможем представить с помощью этого набора. Иначе перейдём к состоянию, что рассмотрены все монеты, стоимость которых не больше Y + 1, и мы можем представить любую сумму до Y + sum включительно.

Заметим, что стоимость максимальной монеты, которую мы рассмотрели, растёт как минимум так же быстро, как числа Фибоначчи. Значит, этот процесс завершится за O (log Answer) итераций.

Чтобы решить исходную задачу, необходимо научиться находить сумму чисел, меньших X, на отрезке. Если делать это за O (log n), то можно решать задачу суммарно за O (m log n log Answer).

Эта задача является стандартной. Рассмотрим метод, который требует линейного количества памяти. Для этого отсортируем все числа в исходном массиве и будем отвечать на все запросы параллельно. На очередной итерации для каждого запроса известно текущее максимальное количество денег, которое можно получить. Отсортируем все запросы по нему. Далее будем добавлять в дерево Фенвика числа исходного массива в порядке возрастания и в нужный момент обновлять границу для очередного запроса.

Задача F
Условие

Ограничение по времени 5 секунд
Ограничение по памяти 256 мегабайт

Гном Паша пишет отборочный раунд Gnome Math Cup. В качестве задачи F предложена следующая.

Дано n натуральных чисел a1,  a2,  …,  an и натуральное число d, требуется найти любой набор ненулевых целых чисел x1,  x2,  …,  xn, такой, что a1×1 + a2×2 + … + anxn = d. Так как у гномов плохо с умножением и сложением, все числа d, ai не превышают 106, а числа xi должны быть от –106 до 106, но не равны 0.

Помогите Паше найти хотя бы один набор xi, который удовлетворяет условию задачи, или сообщите ему, что организаторы сделали плохие тесты и ответа не существует.

Формат входных данных

Первая строка входных данных содержит t — количество тестов. Каждый тест задаётся двумя строками. Первая строка содержит два числа n и d (1 ≤ n ≤ 105, 1 ≤ d ≤ 106). Вторая строка содержит n чисел ai (1 ≤ ai ≤ 106). Сумма n по всем тестам не превосходит 105.

Формат выходных данных

Выведите ответ на каждый тест. Если искомый набор xi существует, то в первой строке выведите YES и во второй выведите любой подходящий набор. Иначе в единственной строке ответа на тест выведите NO.

Примеры

Входные данные
2
2 1
2 3
3 3
2 3 1000

Выходные данные
YES
2 -1
YES
503 -1 -1

Решение

Ответ NO бывает только в одном случае, когда d не делится на наибольший делитель всех чисел ai. В любом другом случае ответ всегда существует. Для начала мы научимся получать хоть какой-то ответ без ограничения на значения, предварительно поделив все ai и d на gcd (a1,  …,  an). Если n = 1, то x1 = d/a1. В других случаях мы будем подбирать для каждого префикса [1,  p] такие xi,  p, что a1×1,  p + … + apxp,  p = gcd (a1,  …,  ap). Делается это индуктивным методом. x1,  1 = 1. Пусть мы уже нашли xi,  p и хотим найти xi,  p + 1. С помощью расширенного алгоритма Евклида мы находим s и t: s • gcd (a1,  …,  ap) + t • ap + 1 = gcd (gcd (a1,  …,  ap),  ap + 1) = gcd (a1,  …,  ap + 1). Тогда для i ≤ p xi,  p + 1 = s xi,  p и xp + 1,  p + 1 = t. Получив xi,  n, вычисляем xi = d/gcd (a1,  …,  an)xi,  n = dxi,  n. Такое решение работает за O (n2), что не подходит под ограничения. Чтобы сократить время работы, мы выберем среди ai подмножество, у которого наибольший общий делитель такой же, как у всего множества, и такое, что нельзя уменьшить. Для этого мы будем перебирать от a1 до an и брать число в подмножество, если оно уменьшает количество различных простых делителей. Таким образом, выбранное подмножество содержит не более 7 элементов, так как максимальное количество простых делителей у числа, меньшего либо равного 106, равно 7. Для чисел из подмножества мы запускаем описанный алгоритм, а для чисел, не вошедших в множество, просто выставляем xi = 0.

Теперь алгоритм работает за O (n), но не выполняются условия, что xi по модулю не превышают 106 и среди них не должно быть нулей. Для этого опишем процедуру нормализации. Сначала выполним для xi первое условие. В первую очередь сделаем все xi для i > 1 неотрицательными и меньшими a1. Это делается простой операцией эквивалентного изменения: мы вычитаем из x1 kai и прибавляем к xi ka1, где k = (xi mod a1 — xi)/a1. Отметим, что результаты выполнения операции влезают в 64-битный тип данных, так как x1 по модулю не может превзойти |d — a2×2 — … — an xn| < 106 • 106 • 105. Теперь пройдёмся по всем xi, начиная со второго, до последнего и с каждым будем последовательно производить операцию: вычесть a1 из xi и прибавить ai к x1. Заметим, что существует i такое, что после применения операции к x1,  …,  xi получилось 0 ≥ x1 ≥ –106. Пусть не существует такого i, тогда все xi стали отрицательными, чего случиться не могло, так как a1×1 + … an xn даёт d, то есть положительное число. После того как мы научились получать |xi| ≤ 106, осталось сделать их ненулевыми. Разобьём все нули на пары, возможно кроме одного. В каждой паре i и j присвоим xi = aj и xj = –ai. У нас, возможно, остался единственный индекс p, для которого xp = 0. Мы рассмотрим несколько случаев:

• Если существует xj, которое по модулю не равно ap, тогда мы применяем операцию: вычитаем sign(xj)ap из xj и прибавляем sign(xj)aj к xp.
• Если же такого xj не существует, но ap ≤ 5 • 105, тогда к любому xj можно применить операцию: прибавить sign(xj)ap к xj и вычесть sign(xj)ap из xp.
• В противном случае должно найтись aq, такое, что aq ≠ ap. Если такого не существует, то все ai = a1, а значит, из-за нормировки на наибольший общий делитель ai = a1 = 1 и должен был выполниться второй случай. Мы проводим операцию: вычтем sign(xj)ap из xq и прибавим sign(xj)aq к xp. После этого xq равно нулю. Но теперь, если n > 2, для q выполнится первый случай, а если n = 2, то для q выполнится второй случай, так как d = aq ap ≤ 106.

Следует отметить, что операцию нормировки нужно производить для каждого префикса в алгоритме, описанном в первом абзаце, чтобы числа помещались в 64-битный тип данных. За дальнейшими подробностями можно обратиться к коду решения жюри, выложенному вместе с тестами.

***
Чемпионат Russian Code Cup входит в число инициатив Mail.Ru Group, направленных на развитие российской IT-отрасли и объединённых ресурсом IT.Mail.Ru. Платформа IT.Mail.Ru создана для тех, кто увлекается IT и стремится профессионально развиваться в этой сфере. Проект объединяет чемпионаты Russian AI Cup, Russian Code Cup и Russian Developers Cup, образовательные проекты Технопарк в МГТУ им. Баумана, Техносфера в МГУ им. М.В. Ломоносова и Технотрек в МФТИ. Кроме того, на IT.Mail.Ru можно с помощью тестов проверить свои знания по популярным языкам программирования, узнать важные новости из мира IT, посетить или посмотреть трансляции с профильных мероприятий и лекции на IT-тематику.

Комментарии (0)