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

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

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

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

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

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

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

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

• Если sum(min_i) > sum(v_i) — ответ «NO»;
• Если sum(max_i) < sum(v_i) — ответ «NO»;
• Нальем в каждую пробирку min_i·p_i / 100 миллилитров реактива c_i;
• После этого для каждого реактива i отсортируем пробирки, для которых c_j = i по возрастанию p_j и будем по очереди наливать в них оставшийся реактив номер i;
• В каждую пробирку нальем еще (max_j - min_j)·p_j / 100 миллилитров i-го реактива или меньше, если он закончится;
• Все оставшееся от реактивов разольем по пробиркам любым способом: в i-ю пробирку суммарно можно налить любое количество жидкости, не превосходящее summary_i·100 / p_i (summary_i — суммарное количество жидкости в ней на текущий момент);
• Если разлить не получилось и жидкость осталась — ответ «NO»;
• Единственная оставшаяся проблема — в каких-то пробирках все еще может быть меньше min_i миллилитров жидкости;
• Для исправления этого в пробирке i, сначала перельем из всех остальных пробирок j реактивы, отличные от c_j, в i-ю пробирку, так, чтобы в j-й пробирке осталось хотя бы min_j жидкости;
• Если и этого не хватило, перельем из остальных пробирок j жидкость номер c_j (теперь это не испортит условие на процентное содержание).

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

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

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

Пусть на очередном шаге мы рассмотрели все монеты, стоимость которых не превышает 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).

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

Ответ «NO» бывает только в одном случае, когда d не делится на наибольший делитель всех чисел a_i. В любом другом случае ответ всегда существует. Для начала мы научимся получать хоть какой-то ответ без ограничения на значения, предварительно поделив все a_i и d на gcd(a₁, ..., a_n). Если n = 1, то x₁ = d / a₁. В других случаях, мы будем подбирать для каждого префикса [1, p] такие x_i, p, что a₁ x_1, p + ... + a_p x_p, p = gcd(a₁, ..., a_p). Делается это индуктивным методом. x_1, 1 = 1. Пусть мы уже нашли x_i, p и хотим найти x_{i, p + 1}. С помощью расширенного алгоритма Евклида мы находим s и t: s·gcd(a₁, ..., a_p) + t·a_p + 1 = gcd(gcd(a₁, ..., a_p), a_p + 1) = gcd(a₁, ..., a_p + 1). Тогда для i ≤ p x_{i, p + 1} = s·x_i, p и x_{p + 1, p + 1} = t. Получив x_i, n, вычисляем x_i = d / gcd(a₁, ..., a_n)·x_i, n = d·x_i, n. Такое решение работает за O(n²), что не подходит под ограничения. Чтобы сократить время работы, мы выберем среди a_i подмножество, у которого наибольший общий делитель такой же как у всего множества и такое что нельзя уменьшить. Для этого мы будем перебирать от a₁ до a_n и брать число в подмножество, если оно уменьшает количество различных простых делителей. Таким образом, выбранное подмножество содержит не более 7 элементов, так как максимальное количество простых у числа меньше либо равного 10⁶ равно 7. Для чисел из подмножества мы запускаем вышеописанный алгоритм, а для чисел не вошедших в множество, мы просто выставляем x_i = 0.

Теперь алгоритм работает за O(n), но не выполняются условия, что x_i по модулю не превышают 10⁶ и среди них не должно быть нулей. Для этого опишем процедуру нормализации. Сначала выполним для x_i первое условие. В первую очередь, сделаем все x_i для i > 1 неотрицательными и меньшими a₁. Это делается простой операцией эквивалентного изменения: мы вычитаем из x₁ ka_i и прибавляем к x_i ka₁, где k = (x_i mod a₁ - x_i) / a₁. Отметим, что результаты выполнения операции влезают в 64-битный тип данных, так как x₁ по модулю не может превзойти |d - a₂ x₂ - ... - a_n x_n| < 10⁶·10⁶·10⁵. Теперь пройдёмся по всем x_i, начиная со второго до последнего, и с каждым будем последовательно производить операцию: вычесть a₁ из x_i и прибавить a_i к x₁. Заметим, что существует i, что после применения операции к x₁, ..., x_i получилось 0 ≥ x₁ ≥  - 10⁶. Пусть не существует такого i, тогда все x_i стали отрицательными, чего случиться не могло, так как a₁ x₁ + ... a_n x_n даёт d, то есть положительное число. Научившись получать |x_i| ≤ 10⁶, осталось сделать их ненулевыми. Разобьём все нули на пары, возможно, кроме одного. В каждой паре i и j присвоим x_i = a_j и x_j =  - a_i. У нас, возможно, остался единственный индекс p, для которого x_p = 0. Мы рассмотрим несколько случаев:

• Если существует x_j, которое по модулю не равно a_p, тогда мы применяем операцию: вычитаем sign(x_j)a_p из x_j и прибавляем sign(x_j)a_j к x_p.
• Если же такого x_j не существует, но a_p ≤ 5·10⁵, тогда к любому x_j можно применить операцию: прибавить sign(x_j)a_p к x_j и вычесть sign(x_j)a_p из x_p.
• В противном случае должен найтись a_q, такой что a_q ≠ a_p. Если такого не существует, то все a_i = a₁, а, значит, из-за нормировки на наибольший общий делитель a_i = a₁ = 1 и должен был выполниться второй случай. Мы проводим операцию: вычтем sign(x_j)a_p из x_q и прибавим sign(x_j)a_qк x_p. После этого x_q равно нулю. Но теперь если n > 2 для q выполнится первый случай, а если n = 2, то для q выполнится второй случай, так как d = a_q a_p ≤ 10⁶.

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