Задача A. Пекарня ≡

Условие

Пекарня города Малоярославца способна произвести до c_i буханок хлеба в i-ый день. При этом каждая буханка хлеба обойдется пекарне в f_i условных Малоярославских долларов. Известно, что для обеспечения города продовольствием в день требуется d_i буханок хлеба, которые успешно будут употреблены населением. Оставшиеся буханки отправляются на склад и могут быть использованы в следующие дни. На складе можно в ночь с i ого на i+1 день хранить не более g_i буханок, при этом хранение каждой буханки хлеба на складе обойдется пекарне в e_i Малоярославских долларов.

Ваша задача — определить наименьшее количество денег, которое пекарня потратит на производство и хранение, чтобы обеспечить Малоярославец хлебом в течение n дней.

Формат входного файла

В первой строке содержится натуральное число n. Далее в n строках содержатся числа c_i, f_i, d_i. Затем в n − 1 строках содержатся числа g_i, e_i.

Формат выходного файла

Выведите единственное число — минимальное количество денег, необходимое пекарне. Если удовлетворить требованиям города невозможно, выведите -1.

Ограничения

1 ≤ n ≤ 10⁵;

0 ≤ c_i, f_i, d_i, g_i, e_i ≤ 10⁹;

Примеры тестов

3
10 1 1
2 2 2
10 10 8
7 2
6 5

73

Задача B. Деление ≡

Условие

Даны числа a и b в 31-ричной системе счисления. Известно, что a делится на b. Найдите последние k цифр частного от деления a на b (также записанного в 31-ричной системе).

Формат входного файла

В первой строке содержится целое положительное число a, состоящее не более чем из миллиона (31-ричных) цифр, записанное в 31-ричной системе счисления (цифры от 0 до 9 соответствуют сами себе, заглавные буквы от 'A' до 'U' соответствуют цифрам от 10 до 30) без ведущих нулей. Во второй строке аналогично записано число b. Гарантируется, что a делится на b без остатка. В третьей строке записано число k.

Формат выходного файла

Выведите ровно k 31-ричных цифр — последние k цифр частного. Если у частного меньше k цифр, дополните его слева ведущими нулями. Все выводимые буквы должны быть заглавными.

Ограничения

1 ≤ k ≤ 10⁴

Примеры тестов

IBCJ
OG
5

000N7

Задача C. Общий предок ≡

Условие

Дан ориентированный граф. Подсчитайте, сколько пар вершин (i,j) имеют общего предка. Общим предком вершин i и j называется такая вершину k, что и i, и j достижимы из k.

Формат входного файла

В первой строке входного файла содержатся целые числа — количество вершин и рёбер в графе. Далее следуют M строк по два числа от 1 до N. Пара чисел (a,b) означает, что из вершины a есть ребро в вершину b.

Формат выходного файла

Выведите одно целое число — количество пар.

Ограничения

1 ≤ N ≤ 10⁴

0 ≤ M ≤ 10⁴

Примеры тестов

2 1
1 2

4

3 2
2 1
3 1

7

Задача D. Числа ≡

Условие

Даны N целых неотрицательных чисел. Мы рассматриваем их попарные суммы (все N² сумм). Для каждого двоичного разряда от 0 до K нужно посчитать, сколько раз в этих суммах в нем стояла единица.

Решение, работающее для K ≤ 20 и N ≤ 10⁶, будет набирать не менее 70 баллов.

Формат входного файла

Числа N, K, P, Q. Последовательность чисел a₀, ... , a_N−1 генерируется так. a₀ = 1, a_i+1 = (a_i ⋅ P + Q) mod 2^K

Формат выходного файла

В первой строке выведите K + 1 целое число — количества единичек в разрядах (Можно было бы вывести остальные количества, не только первые K + 1. Но они нули.) Первым выводить нужно ответ для младшего разряда.

Ограничения

0 ≤ N ≤ 10⁷;

1 ≤ K ≤ 24;

1 ≤ P, Q ≤ 10⁹ + 7;

P и Q — простые;

Примеры тестов

3 10 3 5

4 4 4 5 4 3 0 0 0 0 0

10 3 3 5

50 25 48 16

100 10 17 239

5000 5000 5002 5002 4998 5014 4989 5029 4985 5015 4188

Задача E. T-пути ≡

Условие

Задан неориентированный невзвешенный связный граф G=(V, E) с выделенным множеством вершин T ⊂ V. T-путь — простой путь, начинающийся и заканчивающийся в различных вершинах множества T. Найдите длину кратчайшего T-пути в графе, а также остаток количества различных кратчайших T-путей по модулю 1 000 000 007.

Формат входного файла

В первой строке записаны числа n, m, t — количество вершин, рёбер графа и размер множества T соответственно. На второй строке записаны t различных чисел — элементы множества T. На следующих m строках записаны пары чисел x, y — номера вершин, соединённых ребром (x ≠ y, 1 ≤ x, y ≤ n). В графе нет петель и кратных ребер.

Формат выходного файла

Выведите два числа — длину кратчайшего T-пути и количество различных кратчайших T-путей по модулю 1 000 000 007.

Ограничения

2 ≤ n ≤ 10⁵;

1 ≤ m ≤ 5⋅ 10⁵;

2 ≤ t ≤ n;

Примеры тестов

4 4 2
1 3
1 2
2 3
3 4
4 1

2 2

5 5 3
5 1 3
1 2
2 3
5 2
3 4
4 1

2 4

Задача F. Сильная связность ≡

Условие

Задан ориентированный граф из n вершин и m₁ рёбер. Известно, что в графе есть вершины s и t такие, что все вершины достижимы из s, и из всех вершин достижима t. Также на том же множестве вершин задано другое множество рёбер, состоящее из m₂ элементов. Рёбрам из этого множества приписаны некоторые целые веса.

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

• граф с добавленными рёбрами должен быть сильно связным (каждая вершина должна быть достижима из каждой),
• суммарный вес добавленных рёбер должен быть минимальным.

Формат входного файла

В первой строке находится целое число n. Во второй строке находится целое неотрицательное число m₁. Далее в m₁ строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число m₂. Далее в m₂ строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом — целым числом от −10⁹ до 10⁹, включительно.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 10⁵;

0 ≤ m₁ + m₂ ≤ 5dot 10⁵

Примеры тестов

2
1
1 2
1
2 1 40

YES
40
1
1

2
1
1 2
0

NO

4
5
1 2
1 3
2 3
2 4
3 4
2
4 2 1
3 1 1

YES
2
2
1 2

Задача G. k-почтимонотонность ≡

Условие

Рассмотрим последовательность a₁, …, a_n. Назовём её k-почтимонотонной, если среди неравенств a₁ ≤ a₂, a₂≤ a₃, …, a_n−1≤ a_n ровно k неверных.

Даны числа 0 ≤ b₁, b₂, …, b_m ≤ n, где b₁ + b₂ + … + b_m = n. Найдите количество k-почтимонотонных последовательностей, в которой число 1 встречается b₁ раз, 2 встречается b₂ раз, …, m — b_m раз.

Ответ требуется вывести по модулю 10⁹ + 9.

Формат входного файла

В первой строке заданы два натуральных числа k и m. В следующей строке задано m натуральных чисел b_i.

Формат выходного файла

Выведите единственное число — ответ на поставленную задачу.

Ограничения

1 ≤ k ≤ 100;

1 ≤ m ≤ 26;

1 ≤ b_i ≤ 100;

Примеры тестов

2 2
2 2

1

Задача H. Созвездие Краба ≡

Условие

Недавно учёные обнаружили необычные связи между некоторыми звёздами в созвездии Краба. Задаваемый этими связями граф представляет собой дерево из n вершин. Каждая связь характеризуется мощностью — вещественным числом от 0.5 до 1.

Учёные решили разбить созвездие на k частей по результатам этого исследования. Для этого они исключат из рассмотрения k − 1 связь из данных и будут рассматривать получившиеся деревья. Оптимальным они считают такое разбиение, что:

k−1∑i=1e_i × k∏j=1m_j→ max

Здесь e_i — это мощность i-й исключённой связи, а m_j — количество вершин в j-м из получившихся деревьев.

Формат входного файла

Первая строка входных данных содержит два целых числа n и k. Следующие n − 1 строки содержат по три числа каждая: номера звезд, соединённых связью, а также её мощность. Известно, что мощности связей, а также их структура, случайны.

Формат выходного файла

Выведите с максимально возможной точностью одно вещественное число — значение указанной функции для оптимального разбиения. Ответ считается корректным, если относительная погрешность не превышает 10⁻⁹.

Ограничения

1 ≤ n ≤ 100;

1 ≤ k ≤ n;

Примеры тестов

4 2
1 2 0.56234
2 3 0.85720
3 4 0.84552

3.42879999999999984794

Задача I. Художнег ≡

Условие

Художник Вася Ниимович рисует абстрактные картины. Новая его картина выглядит как прямая, части которой раскрашены в разные цвета. Рисовал он её так. Вначале он нарисовал отрезок первого цвета от точки l₁ до точки r₁. Потом отрезок второго цвета от l₂ до r₂, и так далее. Последний отрезок, нарисованный им, проходил от l_n до r_n и имел цвет с номером n.

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

Формат входного файла

В первой строке написано целое число n. В следующих n строках будут написаны по два целых числа через пробел. В i-ой из этих строк находятся числа l_i и r_i.

Формат выходного файла

В первой строке выведите количество цветов, которые будут видны при оптимальном порядке рисования. Во второй строке должно быть написано n чисел — i-ое число обозначает, какой отрезок надо нарисовать i-ым для достижения оптимального результата. Отрезки нумеруются, начиная с единицы, в том же порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n ≤ 300;

−10⁹ ≤ l_i ≤ r_i ≤ 10⁹

Примеры тестов

4 
1 3
2 4
2 3
1 4

3
4 1 2 3

Задача J. Ромбы ≡

Условие

Дано поле H × W. В некоторых клетках стоят фишки. Нужно выбрать ромб, целиком лежащий на поле, и такой, что он содержит как можно больше фишек, но при этом не содержит ни одной пары фишек, стоящих в клетках с общей стороной.

Формат входного файла

В первой строке заданы через пробел два целых числа H и W (1 ≤ W,  H ≤ 3000). Следующие H строк содержат по W символов каждая. Символ `\t{*}' обозначает фишку, а символ `\t{.}' — её отсутствие.

Формат выходного файла

Выведите четыре числа N, cx, cy и r через пробел — количество покрытых фишек, координаты центра ромба и его радиус (1 ≤ cx ≤ W, 1 ≤ cy ≤ H). Ромб задаётся уравнением |cx − x| + |cy − y| ≤ r. Если оптимальных ответов несколько, можно вывести любой из них.

Примеры тестов

2 3
...
..*

1 3 2 0

3 3
*.*
...
*.*

1 1 1 0

3 3
.*.
*.*
.*.

4 2 2 1

Задача K. Дана строка ≡

Условие

Сотрудник небезызвестного НИИИДС Василий обнаружил, наконец, на своём рабочем месте компьютер. Не будучи слишком опытным пользователем, он не стал использовать все возможности этого загадочного агрегата. Однако из школьного курса Василий помнит, что программисты пользуются таким понятием, как \emph{переменные}. Как ими пользоваться, он не очень помнит, поэтому решил применить одну следующим образом:

• рассмотреть данную строку s
• выбрать некоторую строку t
• заменить некоторые непересекающиеся вхождения t в s на \emph{переменную} A, обозначаемую (что удивительно) заглавной латинской буквой `А', получив строку g.

Формат входного файла

В первой и единственной строке содержится данная строка s (1 ≤ |s| ≤ 10 000). Она состоит из строчных букв латинского алфавита.

Формат выходного файла

Выведите оптимальный набор: в первой строке t, а во второй — g.

Примеры тестов

aaabaaa

aaa
AbA