Задача A. Волшебство на матрицах

Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую матрицу ее префиксной суммой!
   Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл матрицу очень большого размера, каждый элемент которой равен $1$, и очень много раз применил к ней вышеописанное заклинание.
   В этой задаче вам предстоит показать, что ваши навыки программирования ничем не уступуают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в $i$-м ряду в $j$-й строке матрицы после $k$ применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от их деления на 1000000007. Первая строка содержит целое положительное число $Q \; (1 <= Q <= 10^5)$ — количество запросов к вашей программе.
   Каждая из следующих $Q$ строк описывает очередной запрос и содержит три целых положительных числа — номер строки $i$, номер столбца $j$ и количество предварительных применений заклинания $k$ $(1 <= i, j, k <= 10^5)$ соответственно. Выведите $Q$ целых чисел, по одному в строке — значение в ячейке в $i$-м ряду в $j$-й строке матрицы после $k$ применений заклинания, взятое по модулю 1000000007. Подзадача 1 (10 баллов) — $1 <= Q <= 10, 1 <= i, j, k <= 100$
Подзадача 2 (10 баллов) — $1 <= i, j, k <= 100$
Подзадача 3 (10 баллов) — $1 <= i, j, k <= 10^3$
Подзадача 4 (10 баллов) — $i = 1$ или $j = 1$
Подзадача 5 (10 баллов) — $k = 1$
Подзадача 6 (50 баллов) — без дополнительных ограничений Вход

2
2 3 1
1 1 3

Ответ

6
1

Вход

3
4 5 7
3 3 3
2 1 10

Ответ

39600
100
11

   Напомним, что матрица - это двумерный массив (иначе говоря, таблица) содержащий целочисленные значения. Один из возможных примеров матрицы 3x4 приведен ниже: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 3 & 4\\ \hline 4 & 7 & 0 & -2\\ \hline 5 & 9 & 2 & 6\\ \hline \end{tabular} \end{center}
   Префиксной суммой называется матрица, где каждый элемент заменен на сумму чисел в соответствующуем ему прямоугольнике с противоположной вершиной в $(1, 1)$. Более формально, определим префиксную сумму матрицы $A$ как матрицу $B$ такую, что для любых $i > 0, \; j > 0$ выполняется \[B_{i, j} = A_{i, j} + B_{i - 1, j} + B_{i, j - 1} - B_{i - 1, j - 1}\]
   В то время как значения в ячейках $B$ с $i = 0$ или $j = 0$ равны нулю.
   Например перфиксной суммой данной матрицы \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 0 & 1\\ \hline 4 & 1 & 5 & 9\\ \hline 3 & 2 & 6 & 1\\ \hline 0 & 7 & 2 & 4\\ \hline \end{tabular} \end{center}
   Будет следующая матрица: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 3 & 3 & 4\\ \hline 5 & 8 & 13 & 23\\ \hline 8 & 13 & 24 & 35\\ \hline 8 & 20 & 33 & 48\\ \hline \end{tabular} \end{center}

Задача B. Machine Vision

\includegraphics[width=0.25\textwidth,natwidth=360,natheight=300,height=100pt]{abbey_road.png} НурлашКО для своего нового стартапа потребовалось получать текст по фотографии. Так как он только на стадии прототипа, его друг предложил использовать готовое решение предоставляемое платформой Muugle Cloud Vision API. Однако, возникла небольшая проблема в работе с этой платформой. В ответ на отправленную фотографию возвращался не текст, а отдельные слова и их локации в виде прямоугольников. Помогите НурлашКО переупорядочить слова и получить осмысленный текст. Более формально. Вам будет дано $N$ прямоугольников со сторонами параллельными осям координат и слова соответствующие каждому из них. Прямоугольник $B$ является соседом $A$ тогда и только тогда когда площадь пересечения их проекций на ось ординат положительна и $B$ ближайший, слева или справа от $A$, среди всех таких. Строчкой называется максимальное по включению подмножество прямоугольников где от каждого прямоугольника можно добраться до любого другого, возможно переходя по соседям. Высота строчки определяется высотой самого высокого прямоугольника в ней. Выведите все строчки предварительно упорядочив их по высоте в порядке убывания. В самой строчке для каждого прямоугольника выведите соответствующую ему слово в порядке от самого левого к правому. Гарантируется что если $A$ является соседом $B$, то и $B$ является соседом $A$. Соседи для прямоугольника, если таковые есть, всегда определяются однозначно. Смотрите замечание к тестовому примеру для лучшего понимания. Первая строка входного файла содержит единственное целое положительное число $N(1 <=q N <=q 2*10^5)$ — количество прямоугольников. Каждая из следующих $N$ строке содержит строчку из маленьких латинских букв и цифр $s_i (1 <=q |s_i| <=q 100000)$ и четыре целых числа $xl_i$, $yb_i$, $xr_i$, $yt_i$ $(1 <=q xl_i, yb_i, xr_i, yt_i <=q 10^9)$ — слово соответствующее прямоугольнику, координаты левого нижнего и правого верхнего угла соответственно. Гарантируется что сумма длин всех $s_i$ не превосходит $2*10^5$. Также гарантируется что никакие два прямоугольника не пересекаются и не вкладываются, но могут касаться. Выведите ответ на задачу в соответствии с форматом описанным в условии. Каждую строчку следует выводить в отдельной строке. Слова следует разделять единичным пробелом. Данная задача содержит две подзадачи:

1. $1 <=q N <=q 2000$. Оценивается в $30$ баллов.
2. $1 <=q N <=q 200000$. Оценивается в $70$ баллов.

Вход

7
1 9 1 10 3
New 5 3 11 5
Happy 1 2 4 4
2 4 0 5 2
9 10 0 11 2
Year 11 2 15 4
0 6 1 7 3

Ответ

Happy New Year
2 0 1 9

\includegraphics[width=0.5\textwidth,natwidth=610,natheight=450]{example2.png} Обратите внимание, что прямоугольники с цифрами $2$ и $0$ не могут быть соседями для прямоугольника со словом $Happy$. В первом случае площадь проекций $Happy$ и $2$ на ординату равна нулю. Во втором случае хоть и площадь пересечения равна единице, но прямоугольник $New$ находится ближе, в тоже время имея положительную площадь пересечения и именно он будет соседом $Happy$. Расстояние между двумя прямоугольниками $A$ и $B$ - это кратчайшее среди всех попарных расстояний от множества точек ограниченных прямоугольником $A$ до множества точек ограниченного прямоугольником $B$.

Задача C. Хан и массив

Хан на день рождения получил массив из $n$ элементов. И начал с ним играться. Он взял каждый элемент и записал $m$ раз. Также у Хана есть любимое простое число $P$. Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на $P$. Помогите Хану узнать сколько таких подпоследовательностей. В первой строке даны три целых числа $n$, $m$, $P$ через пробел — размер массива Хана; количество раз, которое он записывает каждое число в массиве; и простое число соответственно $(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$. Во второй строке даны $n$ целых чисел $a_1, a_2, ..., a_n$ — полученный Ханом массив на его день рождения $(1 <= a_i <= 10^9)$. Выведите одно число — количество подпоследовательностей, которые в сумме делятся на $P$. Так как это число может быть большим, выведите его остаток от деления на $1000000007$. Подзадача 1 (10 баллов) — $ n <= 10^5$, $m <= 10^5,$ $P = 2 $. Подзадача 2 (10 баллов) — $ n * m <= 20$, $P <= 1000 $. Подзадача 3 (10 баллов) — $ n * m * P <= 10^6, $. Подзадача 4 (20 баллов) — $ n * m <= 250000$, $P <= 500 $. Подзадача 5 (50 баллов) — $ n <= 10^5$, $m <= 10^9$, $P <= 1000 $. Вход

3 2 5
3 7 4

Ответ

11

Хан преобразует изначальный массив следующим образом. Пусть $a_1, a_2, ..., a_n$ будет изначальным массивом. И заведем пустой массив $b$. Один за одним, слева направо будем обрабатывать элементы массива $a$ и элемент $a_i$ припишем к $b$ ровно $m$ раз. Хан будет решать задачу над полученным массивом $b$. Подпоследовательность — последовательность, которая получается путем удаления нескольких, возможно ноль, элементов изначальной последовательности. В первом примере, массив $b$ будет выглядеть следующим образом: $3, 3, 7, 7, 4, 4$. Вот все $11$ подпоследовательности, сумма которых делится на $5$: $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 3, 4]$, $[3, 3, 4]$, $[3, 3, 7, 7]$, $[7, 4, 4]$, $[7, 4, 4], $[3, 7, 7, 4, 4], $[3, 7, 7, 4, 4]$.

Задача D. Чередующие тренировки

Алан очень сильно любит решать задачи по программированию и играть шахматы. В обоих сферах он хочет преуспеть, стать легендарным гроссмейстером. Айдос как опытный тренер предложил ему у него потренироваться.
   У Айдоса определенное расписание на каждый из следующих $n$ дней. В каждый из дней Айдос тренирует только один вид, либо программирование, либо шахматы. Алан хочет выбрать несколько подряд идущих дней для тренировки. Также Алан заметил, что если два дня подряд тренироваться в одной и той же сфере, то он устает, т.е. Алану надо чередовать шахматы и программирование. Помогите Алану выбрать максимальное количество подряд идущих дней так, чтобы он за этот период не устал тренироваться. Первая строка входных данных содержит целое цисло $n$ ($1 <= n <= 2\cdot 10^5$) — количество тренировочных дней у Айдоса. Вторая строка содержит $n$ цифр $0$ или $1$ без пробелов — $i$-я цифра $0$ если в $i$-й день Айдос тренирует программирование, иначе Айдос тренирует шахматы. Выведите одно число — максимальное количество подряд идущих тренировочных дней для Алана. В данной задаче 50 тестов, прохождение каждого теста оценивается в 2 балла:
Подзадача 1: 2 тестовых примера из условия
Подзадача 2: $n <= 3$. 13 тестов
Подзадача 3: $n <= 100$. 5 тестов
Подзадача 4: $n <= 5000$. 12 тестов
Подзадача 5: $n <= 200000$. 18 тестов Вход

4 0
1010

Ответ

4

Вход

5 3
01011
1 3
2 5
4 5

Ответ

3

В первом тесте Алан может все дни тренироваться. Во втором тесте Алан может тренироваться со 2-го по 4-й день: во 2-й день программирование, в 3-й день шахматы и в 4-й день программирование. Заметим, что первый, второй день Алан не может тренироваться, так как в эти дни только программирование и Алан сильно устанет.

Задача E. Меж двух миров

Алан живет в мире под номером $A$. Нурдаулет живет в мире под номером $B$. В мире $A$, если одна строка является префиксом другой, то они считаются одинаковыми. У Нурдаулета есть $n$ строк, он хочет узнать количество неупорядоченных пар $i, j$ таких, что Алану они покажется одинаковыми. Помогите Нурдаулету с задачей. Обозначим $|s|$ как длину строки $s$. Строка $s$ является префиксом строки $t$, если $|s| <= |t|$ и строка $s$ равна строке, образованной из первых $|s|$ символов строки $t$. В первой строке дается единственное число $n (1 <= n <= 100000)$ — количество строк. В следующих $n$ строках дается по одной строке $s_i$. Гарантируется, что суммарная длина строк не превышает $500000$. Выведите единственное число — ответ на задачу. В 40 процентах тестов $n <= 100$. В 20 процентах тестов, длины всех строк равны. Вход

3
ab
abc
ab

Ответ

3

Задача F. Yosik - город где сбываются мечты

Yosik - это город Казахстана где сбываются мечты миллионов. И при этом Yosik - важнейший экономический центр всего мира. Yosik, наряду с Лондоном и Токио, называют одним из трёх основных центров мировой экономики. Ну конечно же, без мэра CMaster город не был бы таким популярным. Он приложил все свои усилия чтобы достичь этого. Но экономическая война между другими странами повлиял негативно на экономику Yosik-a. Мэр хочет улучшить качество некоторых дорог в городе. И в городе существует $n$ районов. Каждый район имеет экономический статус: Высокий или Низкий. И чтобы мэр CMaster принял правильное решение об улучшении дорог во время кризиса в городе он должен узнать сколько пар Высоких важности районов это дорога соединяет. То есть, дорога соединяет два Высоких важности районов $(a, b)$ если и только если все пути между этими двумя районами проходят через эту дорогу. И есть $q$ событии двух видов: 1) Сделать статус района $v$ $(1 <=q v <=q n)$ Высоким если он Низкий, а иначе сделать его Низким. 2) Для дороги $i$ сказать количество пар районов $(a, b)$ с Высоким статусом что дорога $(1 <=q i <=q m)$ лежит на всех путях между этими районами $(a, b)$. И при этом пары $(a, b)$ и $(b, a)$ считаются одинаковыми Город можно представить как связный неориентированный граф с $n$ вершинами и $m$ ребрами. Где вершина это район а ребро это дорога. Каждый район имеет статус экономического важности либо Высокий либо Низкий. Вначале все районы имеют Низкий важность для экономики. Из района может существовать дорога которая соединяет район с собой (петля), но не существует кратные ребра, то есть дороги которые соединяют одинаковую пар вершин. На первой строке даны 3 числа $n$, $m$ и $q$, количество районов, дорог и событии, соответственно. Далее следует $m$ чисел - неориентированные ребра в Yosik-e. В графе не существует две одинаковых ребер, но могут быть петли Потом вам дается запросы в виде $(type, number)$. Если $type = 1$, то это первый тип запросов и $number$ означает номер вершины, $(1 <=q number <=q n)$. А если $type = 2$, то это второй тип запросов и число означает номер ребра в порядке входных данных, $(1 <=q number <=q m)$ Для каждого запроса вида 2, вы должны вывести количество пар город $(a, b)$ которые имеют статус Высокой важности что ребро $i$ лежит на всех путях между этими вершинами $(a, b)$ Данная задача содержит четыре подзадач: 1. $1 <=q n, q <=q 10$. Подзадача оценивается в 10 баллов 2. $1 <=q n, m, q <=q 300$. Подзадача оценивается в 14 баллов 3. $1 <=q n, m, q <=q 2000$. Подзадача оценивается в 22 баллов 4. Город является деревом $1 <=q n, q <=q 10^5, m = n - 1$. Подзадача оценивается в 24 баллов 5. $1 <=q n, m, q <=q 10^5$. Подзадача оценивается в 30 баллов Вход

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

Ответ

0
2
9
0

Граф из первого теста (перед запросом с номером 5)

Можно заметить что выделенная ребро (ребро с индексом 1) соединяет 2 пары вершин: (1, 2) и (1, 4) Но, еще заметим что ребро (2, 4) не соединяет вершины 2 и 4 так как существует путь (2 -> 3 -> 4).