Задача A. Странные строки ≡

Условие

Рассмотрим строку S, состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».

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

Например, W(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.

Подпоследовательностью строки S называется строка, которую можно получить из S удалением произвольного числа символов. Обозначим как Y(S) множество, состоящее из всех возможных подпоследовательностей строки S. Аналогично W(S), каждая подпоследовательность строки S включается в Y(S) ровно один раз, даже если она может быть получена несколькими способами удаления символов из строки S. Поскольку любая подстрока строки S является также ее подпоследовательностью, то множество Y(S) включает в себя W(S), но может содержать также и другие строки.

Например, Y(«abba») = W(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.

Будем называть строку S странной, если для нее W(S) = Y(S). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее W(«abb») = Y(«abb») = {«a», «b», «ab», «bb», «abb»}.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке S в качестве подстроки несколько раз. Так, странность строки «abba» равна 7, поскольку любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке S определяет ее странность.

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

Входной файл содержит строку S, состоящую из строчных букв латинского алфавита.

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

Выходной файл должен содержать одно целое число: странность заданной во входном файле строки.

Ограничения

Строка S имеет длину от 1 до 200 000 символов.

Система оценки и описание подзадач

В этой задаче четыре подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (29 баллов)

Строка S состоит только из букв «a» и «b». Длина строки S не превышает 50.

Подзадача 2 (12 баллов)

Длина строки S не превышает 50.

Подзадача 3 (25 баллов)

Длина строки S не превышает 1000.

Подзадача 3 (34 балла)

Длина строки S не превышает 200 000.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

abba

7

Задача B. Интересные числа ≡

Условие

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 — интересные.

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 10⁹ + 7.

Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 10⁹ + 7.

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

Входной файл содержит две строки. Первая строка содержит число L, вторая строка содержит число R.

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

Выходной файл должен одно целое число — остаток от деления количества интересных чисел, лежащих в диапазоне от L до R включительно, на 10⁹ + 7.

Ограничения

1 ≤ L ≤ R ≤ 10¹⁰⁰

Описание подзадач и системы оценивания

Подзадача 1 (21 балл)

L = 1, R ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (22 балла)

1 ≤ L ≤ R ≤ 10¹⁸.

В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (24 балла)

L = 1, R = 10^k для некоторого целого k, 2 ≤ k ≤ 100.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (33 балла)

1 ≤ L ≤ R ≤ 10¹⁰⁰.

В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

1
100

54

Задача C. Укладка плитки ≡

Условие

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 10⁹ + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹ + 7.

Пояснения к примерам

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

Рисунок 1. Все способы укладки плиток в первом примере

Рисунок 2. Все способы укладки плиток в третьем примере. Уже уложенная плитка отмечена серым цветом.

Система оценивания и описание подзадач

Подзадача 1 (20 баллов)

1 ≤ n ≤ 8, k = 0

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 2 (20 баллов)

1 ≤ n ≤ 1000, k = 0

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 3 (20 баллов)

1 ≤ n ≤ 100 000, k = 0

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 4 (40 баллов)

1 ≤ n ≤ 100 000, 1 ≤ k ≤ 2 n

В этой подзадаче 20 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток.

Последующие k строк содержат по два целых числа x_i и y_i, которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на x_i-м метре коридора в y_i-м ряду.

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

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

Ограничения

1 ≤ n ≤ 100 000; 0 ≤ k ≤ 2 n; 1 ≤ x_i ≤ n; 1 ≤ y_i ≤ 2.

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

2 0

7

3 0

22

3 1
2 1

8

Задача D. Делители ≡

Условие

Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из k чисел (a₁, a₂, …, a_k), если выполнены следующие условия:

1. каждое из чисел a_i является делителем числа n;
2. выполняется неравенство a₁ < a₂ < … < a_k;
3. числа a_i и a_i+1 для всех i от 1 до k − 1 являются взаимно простыми;
4. произведение a₁ a₂… a_k не превышает n.

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

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

Система оценивания

Правильные решения для тестов, в которых n ≤ 1000 и k = 2, оцениваются из 30 баллов.

Правильные решения для тестов, в которых k = 2, оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая n ≤ 1000 и k = 2).

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

Первая строка входного файла содержит два целых числа: n и k.

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

В выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа n.

Ограничения

2 ≤ n ≤ 10⁸

2 ≤ k ≤ 10

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

90 3

16

10 2

4

Задача E. Максимальный поток (несколько истоков и стоков) ≡

Условие

Требуется найти максимальный поток в сети с несколькими истоками и стоками.

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

В первой строке входного файла содержится число N  — количество вершин в сети. Далее следует N чисел a_i ∈ 0, 1, 2. Если a_i = 0, то i-ая вершина  — это обычный узел; если a_i = 1 то i-ая вершина  — это исток; если a_i = 2 то i-ая вершина  — это сток. Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.

Далее следует матрица целых чисел U размером N × N. 0 ≤ U_ij ≤ 10⁶  — вместимость ребра из i-ой вершины в j-ую. На диагонали матрицы находятся нули.

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

В выходной файл выведите единственное число  — объем максимального потока.

Ограничения

2 ≤ N ≤ 50

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

2
1 2
0 100
1000 0

100

4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0

3

10
0 0 1 0 1 2 2 0 2 0 
0 100 0 0 0 1 0 0 0 0
0 0 0 0 0 120 0 0 0 0
100 0 0 0 0 0 0 0 0 0
10 10 0 0 0 0 0 20 0 20
0 0 0 50 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 15 0 15 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0

141

Задача F. Полезные ископаемые ≡

Условие

Ведется проект по освоению планеты соседней звездной системы. Для добычи полезных ископаемых планируется направить на планету несколько партий роботов.

Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером w на h, клетки участка имеют координаты от (1, 1) до (w, h). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено s баз, и i-я база находится в клетке с координатами (x_i, y_i).

Каждая партия роботов характеризуется тремя параметрами: j-я партия доставляется на базу b_j, содержит n_j роботов и каждый робот партии обладает мобильностью m_j.

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

Рис. 1. Возможные перемещения робота в восьми направлениях.

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

Руководством проекта получена информация о t партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше q роботов. Поэтому руководство должно выбрать k первых партий роботов, где 0 ≤ k ≤ t, которые будут полностью доставлены на соответствующие базы. После этого, если k < t, следует дополнительно принять z из n_k + 1 роботов следующей, (k + 1)-й партии, 0 ≤ z < n_k + 1.

Все полученные таким образом роботы должны с учетом ограничения на мобильность разместиться на участке таким образом, чтобы в каждой клетке было не более q роботов. После этого они будут активированы и начнут добычу полезных ископаемых. Разумеется, руководство проекта старается максимизировать количество роботов, которые будут доставлены на планету, поэтому, с учетом описанных ограничений, требуется максимизировать k, а затем максимизировать z.

Требуется написать программу, которая по размерам участка, числу q, описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число k — количество партий роботов, и затем – максимальное число z – дополнительное количество роботов из (k + 1)-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более q роботов.

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

Первая строка входного файла содержит числа w, h, s и q. Последующие s строк содержат по два целых числа x_i, y_i и описывают базы специалистов (1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h).

Следующая строка содержит число t — количество партий роботов. Последующие t строк описывают партии роботов и содержат по 3 целых числа: b_j, n_j и m_j (1 ≤ b_j ≤ s, 1 ≤ n_j ≤ w × h × q, 0 ≤ m_j < max(w, h)).

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

Требуется вывести два числа: k и z, 0 ≤ k ≤ t. Если k = t, то z должно быть равно 0, иначе должно выполняться условие 0 ≤ z < n_k + 1.

Ограничения

1 ≤ w, h ≤ 10⁵, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,

Пояснение к примеру

В приведенном примере описания входных данных следует полностью принять первую партию роботов и дополнительно принять 7 роботов из второй партии. На рис. 2 показано, как можно разместить этих роботов на участке, чтобы в каждой клетке было не более одного робота. Базы специалистов показаны кружками. Клетки, в которых окажутся роботы с базы 1, показаны вертикальной штриховкой, а клетки, в которых окажутся роботы с базы 2, показаны серым цветом.

Рис. 2. Возможное размещение роботов на участке в данном примере.

Описание подзадач и системы оценивания

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

Тесты для подзадачи 6 запускаются только в случае, если все тесты подзадач 1–5 успешно пройдены. Каждый тест в подзадаче 6 оценивается независимо в 1 балл.

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

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

4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2

1 7