Задача A. Очередь

Бекжану рассказали об одной интересной очереди. Это очередь в кассу, в которой работает не особо добросовестный кассир. Кассир в этой очереди обслуживает клиента, только когда клиент ругается с ним. Время от времени кто-то из очереди осознает, что он опаздывает на очень важную встречу, проходит вне очереди, ругается с кассиром, после чего кассир его обслуживает. Допустим, что человека, прошедшего вне очереди зовут Ануар. Каждый человек, стоявший перед Ануаром в очереди, выразит свое недовольство его поступком в виде какого-то количества слов (фиксированного для каждого говорящего). Наблюдавшему за очередью Бекжану стало интересно, сколько же нелестных слов в свой адрес услышит каждый, прошедший вне очереди? Первая строка входных данных содержит целое число $N$ ($2 \leq N \leq 5 \cdot 10^5$) — число событий в очереди. Описание каждого из событий начинается с целого числа $type$ ($1 \leq type \leq 2$). Если $type = 1$, то за ним следует целое число $w$ ($1 \leq w \leq 10^9$). Данный тип запросов означает, что новый человек пришел в очередь. Его номером является наименьшее целое положительное число, не использованное до этого в качестве номера, а количеством слов, которые он будет произносить при каждом недовольстве — число $w$. Если $type = 2$, то за ним следует целое число $x$. Данный тип запросов означает, что человек с номером $x$ проходит вне очереди. Гарантируется, что в момент запроса человек с таким идентификатором присутствует в очереди. Гарантируется, что хотя бы один человек покинет очередь. Для каждого прошедшего вне очереди человека выведите, сколько слов возмущения он услышит из очереди.

1. $N \le 20$, $w \le 1000$. Стоимость подгруппы: $10$ баллов.
2. $N \le 10000$. Стоимость подгруппы: $40$ баллов.
3. $N \le 500000$. Стоимость подгруппы: $50$ баллов.

Вход

2
1 1
2 1

Ответ

0

Вход

8
1 8
1 1
1 9
2 2
1 2
1 4
2 5
1 3

Ответ

8
19

В первом примере человек пришел в очередь, поругался с кассиром и не выслушивал слов ни от кого. Во втором примере в очередь сначала придут люди, которые скажут $8$, $1$ и $9$ слов недовольства соответственно (и получат номера $1$, $2$ и $3$ соответственно). Затем человек с номером $2$ пройдет вне очереди и выслушает недовольство от человека с номером $1$ ($8$ слов). После этого в очередь придут люди с количествами слов $2$ и $4$, и номерами $4$ и $5$ соответственно. Затем человек с номером $5$ пройдет вне очереди и выслушает недовольство от людей с номерами $1$, $3$, $4$ ($19$ слов). Последним в очередь придет человек с номером $6$ и количеством слов $3$

Задача B. Яблоки

Тима и его $N - 1$ друзей собирали яблоки. Для удобства пронумеруем всех числами от $1$ до $N$. У Тимы номер $1$. Тима заметил, что у него яблок больше чем у его друзей, и решил поделиться своими яблоками. Он дал всем остальным столько яблок, сколько у них было. Т.е если у кого-то было $X$ яблок, то Тима дал ему еще $X$ яблок. Затем человек с номером $2$ дал всем столько, сколько у них имелось на тот момент. И так далее до $N$-го человека. И в результате у всех оказалось одинаковое количество яблок. Тима хочет знать сколько яблок было у каждого в начале. Он помнит, что в начале у него было $A_1$ яблок. В первой строке входных данных записано одно целое число $T(1\le T \le 1000)$ - количество тестов. В следующих $T$ строках находится по два целых числа $N$ ($1 \le N \le 50$),$1\le A_1\le 10^{16}$. Выведите $T$ — строк, в каждой строке выведите $-1$ если такое случае невозможно. Иначе выведите $N$ чисел $A_1,A_2, .., A_N$. Если существует несколько возможных ответов, выведите любой из них. Данная задача содержит четыре подзадачи:

1. $1 \le T \le 50, N = 2, 1 \le A_1 \le 10^6$. Оценивается в $10$ баллов.
2. $1 \le T \le 50, N = 3, 1 \le A_1 \le 10^9 $. Оценивается в $15$ баллов.
3. $T = 1, 1 \le N \le 50, 1 \le A_1 \le 10^5$. Оценивается в $30$ баллов.
4. $1 \le T \le 1000, 1 \le N \le 50, 1 \le A_1 \le 10^{16}$. Оценивается в $45$ баллов

Вход

2
3 13
2 10

Ответ

13 7 4 
10 6 

Первый тест: В начале 13, 7, 4. После 1-го : 2, 14, 8. После 2-го : 4, 4, 16. После 3-го: 8,8,8.

Задача C. Саперы

Два сапера должны обезвредить все мины в минном поле. Поле представляет собой таблицу $n \times m$ ($n$ строк и $m$ столбцов), и в каждой клетке этой таблицы находится не больше одной мины. Строки таблицы пронумерованы от $1$ до $n$ сверху вниз, столбцы пронумерованы от $1$ до $m$ слева направо. Саперы хотят разделить все поле на двоих максимально справедливым образом, так чтобы части были равными (при каком-то повороте они должны совпасть) и разница в количестве мин в частях была минимальной. Делить можно только по границам клеток и части должны быть связными, т.е. из каждой клетки одной части можно дойти до любой другой клетки этой же части передвигаясь только по соседним по стороне клеткам одной части. Вам надо написать программу, которая будет делить поле на две части для саперов максимально справедливым образом. Гарантируется, что $m$ четное число. Первая строка входных данных содержит два целых числа $n$($1\le n \le 1000$) и $m(1 \le m \le 1000)$. В каждой из следующих $n$ строк следуют по $m$ символов — описание поля. Если символ равен «.», то текущая клетка пустая. Если символ равен «*», то в этой клетке находится мина. Выведите $n$ строк по $m$ символов «1» или «2» обозначающее какому саперу достанется текущая клетка. В данной задаче ровно 100 тестов. За каждый пройденный тест участник получает $1$ балл. Вход

5 8
**.....*
...*.*..
*..*....
*....*..
.......*

Ответ

11111111
22222211
22112211
22111111
22222222

Задача D. Красивая последовательность

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Вам даны две последовательности целых неотрицательных чисел размера $n$: $a_1, a_2, \ldots, a_n$ и размера $m$: $b_1, b_2, \ldots, b_m$. Назовем последовательность из $k$ целых чисел $c_1, c_2, \ldots, c_k$ красивой, если выполняются следующие условия:

• k является нечетным.
• $c_{2*j-1} < c_{2 * j}$ и $c_{2*j+1} < c_{2 * j}$ для всех $1 < 2 * j < k$.
• Последовательность $c_1, c_2, \ldots, c_k$ является подпоследовательностью последовательности $a_1, a_2, \ldots, a_n$.
• Последовательность $c_1, c_2, \ldots, c_k$ является подпоследовательностью последовательности $b_1, b_2, \ldots, b_m$.

Найдите максимальную длину красивой последовательности и количество различных красивых последовательностей максимальной длины по модулю $10^9 + 9$. В первой строке входных данных дано целое положительное число $n$ ($1 \le n \le 10^4$)~— размер последовательности $a$. Вторая строка содержит $n$ целых неотрицательных чисел $a_i$ ($1 \le a_i \le 20000$)~— последовательность $a$. В третьей строке содержится целое положительное число $m$ ($1 \le m \le 10^4$)~— размер последовательности $b$.Четвертая строка содержит $m$ целых неотрицательных чисел $b_i$ ($1 \le b_i \le 20000$)~— последовательность $b$. Числа в обеих последовательностях задаются через одиночный пробел. Выведите два целых числа ответ на задачу. Если ответа несуществует выведите два нуля. Данная задача содержит четыре подзадачи:

1. $1 \leq n \leq 20$, $1 \le m \le 10$. Оценивается в $9$ баллов.
2. $1 \leq n \leq 1000$, $1 \le m \le 20$. Оценивается в $9$ баллов.
3. $1 \leq n \leq 500$, $1 \le m \le 500$. Оценивается в $28$ баллов.
4. $1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Оценивается в $54$ баллов.

Вход

1
1
1
2

Ответ

0 0

Вход

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

Ответ

3 6

Вход

4
1 1 3 2
4
1 3 2 2

Ответ

3 1

Задача E. Перевороты

На столе подряд лежат $K$ листов бумаги. Дано число $N$. На каждом листе записаны все числа от 1 до $N$ ровно по одному разу, но некоторые из них записаны на видимой стороне, а остальные на обратной. Ваша задача - перевернуть некоторые листы так, чтобы максимизировать количество различных чисел на видимых сторонах. На первой строке даны $N$ и $K$, так чтобы $N \times K\le 10^6$ при этом $ N \ge 1 $ и $K \ge 1$. На следующих $K$ строках идут описания листов. На $i+1$ строке, первое число это $m$ ($0 \le m \le N$) — количество чисел записанных на видимой стороне $i$-ого листа бумаги. Далее идут $m$ чисел которые написаны на видимой стороне $i$-го листа, каждый от $1$ до $N$. Выведите строку состоящий из $K$ символов. $i(1 \le i \le K)$ символ равняется 1 если надо перевернут, иначе 0. Если существует несколько ответов, вывести любой. Данная задача содержит пять подзадач:

1. $1 \leq N \leq 10$, $1 \le K \le 10$. Оценивается в $11$ баллов.
2. $1 \leq N \le K$. Оценивается в $8$ баллов.
3. $1 \leq N \leq 100$. Оценивается в $15$ баллов.
4. $1 \leq N \times K \leq 5 \cdot 10^4$. Оценивается в $30$ баллов.
5. $1 \leq N \times K \leq 10^6 $. Оценивается в $36$ баллов.

Вход

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

Ответ

1111

Вход

6 2
3 1 3 4
3 1 2 4

Ответ

01

Задача F. Обещаю, последняя задача с деревом :)

Дано подвешенное бинарное дерево изначально состоящее из одной вершины с номером 1. Вам предстоит обработать $M$ запросов следующих типов :

• $Grow$ $V$. К каждому листу $leaf$ в поддереве вершины $V$ дописать две новые вершины с номерами $2 \cdot leaf$ и $2 \cdot leaf+1$.
• $Sum$ $V,$ нужно подсчитать сумму номеров вершин в поддерево вершины $V$ по модулю $10^9+7$.

Получится ли у Вас решить эту задачу? Первая строка входного файла содержит целое число $M$ $(1 \leq M \leq 2 \cdot 10^5)$ — количество запросов. В последующих $M$ строках содержится описания операций. Каждая операция описывается строкой $Op$ $V$, где $Op$ — тип операции ($Grow$ либо $Sum$), а $V$ — номер вершины для которой она выполняется. Для каждой операции типа $Sum$ в выходной файл на отдельной строке необходимо вывести соответствующую сумму. Выводите операции в том же порядке в котором они идут во входном файле. Данная задача содержит семь подзадач:

1. $1 \leq M \leq 20$. Оценивается в $15$ баллов.
2. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Grow$ $V$. Оценивается в $10$ баллов.
3. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Sum$ $V$. Оценивается в $10$ баллов.
4. $1 \leq M \leq 10^3$. Оценивается в $15$ баллов.
5. $1 \leq M \leq 2 \cdot 10^5$, гарантируется что все запросы $Sum$ идут строго после всех запросов $Grow$. Оценивается в $15$ баллов.
6. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^6$. Оценивается в $15$ баллов.
7. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^9$. Оценивается в $20$ баллов.

Вход

5
Grow 1
Grow 1
Grow 2
Sum 1
Sum 4

Ответ

66
21

Задача G. Секретные алгоритмы

В стране Timart есть $N$ городов и $M$ двусторонних дорог. Города пронумерованы от $1$ до $N$. Известно, что с каждого города можно добраться до любого другого по существующим дорогам. Андрей спрятал свитки с секретными алгоритмами в городах Timart. В $i$-ом городе хранится $A_i$ свитков. Рамазан хочет украсть эти свитки. Он может украсть все свитки из города, в котором он находится. Рамазан может начать воровать с любого города. Чтобы не быть пойманным, он не будет использовать одну дорогу два раза подряд. Свитки каждого города можно украсть не более одного раза, посещать города можно по несколько раз. Помогите Рамазану украсть как можно больше свитков. В первой строке входных данных содержится два целых числа $N$, $M$ ($1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$). Во второй строке находятся $N$ целых чисел $A_1, A_2, \ldots, A_N$, где $A_i$ — количество свитков в $i$-ом городе. В следующих $M$ строках содержится по $2$ целых положительных числа, разделенных пробелом, $u_i$, $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)— дорога соединяющая города $u_i$ и $v_i$. Известно, что между двумя городами не может быть больше одной дороги, и что никакая дорога не соединяет город с самим собой. Гарантируется, что между любыми двумя городами существует путь состоящий из заданных дорог Выведите одно целое число — максимальное количество свитков, которое может украсть Рамазан. Данная задача содержит пять подзадач:

1. $1 \le N \le 100$,$M = \frac{N \cdot (N - 1)}{2}$, $1 \le A_i \le 300$, для всех $1 \le i \le N$. Оценивается в $7$ баллов.
2. $1 \le N \le 12$, $0 \le M \le 66$, $1 \le A_i \le 300$, для всех $1 \le i \le N$. Оценивается в $12$ баллов.
3. $1 \le N \le 10^5$, $M = N - 1$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $12$ баллов.
4. $3 \le N \le 10^5$, $M = N$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $25$ баллов.
5. $1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $44$ балла.

Вход

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

Ответ

35

Задача H. Тима и сумма степеней

У Тимы есть целое число $N$ и массив $A$ из $N$ целых чисел. Также у него есть два целых числа $M$ и $K$. Для каждого $i$ от $1$ до $N$-$M$+$1$ Тима хочет посчитать значение выражения $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$. Помогите ему решить эту задачу. В первой строке находятся три целых числа $N$($1 \le N \le 10^5$),$M$($1 \le M \le N$) и $K$($0 \le K \le 20$). Во второй строке находятся $N$ целых числа $A_1,A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$). Выведите $N$-$M$+$1$ строк, в $i$-ой строке выведите остаток $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$. при делении на $10^9 + 7$. Данная задача содержит пять подзадач:

1. $1 \le N \le 100, 0 \le K \le 3,1 \le A_i \le 10$. Оценивается в $7$ баллов.
2. $1 \le N \le 10^4, 0 \le K \le 20,1 \le A_i \le 10^9$. Оценивается в $12$ баллов.
3. $1 \le N \le 10^5, 0 \le K \le 1,1 \le A_i \le 10^9$. Оценивается в $13$ баллов.
4. $1 \le N \le 10^5, K = 2,1 \le A_i \le 10^9$. Оценивается в $20$ баллов.
5. $1 \le N \le 10^5, 0 \le K \le 20,1 \le A_i \le 10^9$. Оценивается в $48$ баллов

Вход

5 3 2
1 2 3 4 5

Ответ

36
50
64

Вход

3 2 0
7 3 2

Ответ

10
5

Пояснение к примеру 1: При $i = 1$, $1^K \cdot A_1 + 2^K \cdot A_2 + 3^K \cdot A_3$ = $1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 3 = 1 + 8 + 27 = 36$. При $i = 2$, $1^K \cdot A_2 + 2^K \cdot A_3 + 3^K \cdot A_4$ = $1^2 \cdot 2 + 2^2 \cdot 3 + 3^2 \cdot 4 = 50$. При $i = 3$, $1^K \cdot A_3 + 2^K \cdot A_4 + 3^K \cdot A_5$ = $1^2 \cdot 3 + 2^2 \cdot 4 + 3^2 \cdot 5 = 64$.