Задача A. Магический квест

Вы играете в компьютерную игру. У вас имеется $N$ магических предметов разного размера. В дорожную сумку могут поместиться только предметы суммарным размером $K$. Также вы знаете $M$ заклинаний, каждое из которых имеет определенную силу и использует определенный набор из имеющихся предметов. Отправляясь в поход, вы должны заполнить сумку предметами так, чтобы суммарная сила заклинаний, которыми вы сможете воспользоваться была максимально возможной. Первая строка входного файла содержит три целых числа $N,$ $M,$ $K$ $(1 \le N,M \le 20,$ $1 \le K \le 10^9).$ Следующая строка содержит $N$ положительных целых чисел, не превышающих $10^9$ — размеры предметов. Следующая строка содержит $M$ положительных целых чисел, не превышающих $10^9$ — силы заклинаний. Следующие $M$ строк содержат описание заклинаний, по одному на строке. Описание заклинания — список номеров предметов, необходимых для того, чтобы воспользоваться им. Каждое заклинание требует хотя бы одного предмета. Выведите одну строку — список номеров предметов, которые вы возьмете с собой. Вход

3 3 2
1 1 1
10 100 1000
1 2
1 2
3 2

Ответ

2 3

Задача B. Ферзи

На шахматной доске $N \times N$ написаны числа — по одному на каждой ячейке. Расставьте $N$ ферзей так, чтобы они не били друг друга (один ферзь бьет другого, если они стоят на одной горизонтали, вертикали или диагонали) и чтобы сумма чисел на занятых ячейках была максимально возможной. Первая строка входного файла содержит одно целое число $N$ $(1 \le N \le 12).$ Каждая из следующих $N$ строк содержит по $N$ неотрицательных целых чисел, не превышающих 1000, — описание доски. Числа в строках разделены пробелами. Выходной файл должен содержать ровно $N$ строк по $N$ чисел в каждой. $j$-е число $i$-й строки должно быть 1, если в ячейке $(i, j)$ стоит ферзь, и 0 в противном случае. Вход

4
1 2 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Ответ

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Задача C. Слияние

Идет слияние двух компаний. В первой $n$ рабочих, а во второй $m.$ Новое руководство хочет оставить только людей, которые не знакомы с рабочими другой компании. Вам известно, кто с кем знаком в разных компаниях. Найдите максимальное количество рабочих, которое новое руководство может оставить. В первой строке входного файла заданы два целых числа $n$ и $m$ $(1 \le n,m \le 50).$ В следующих $n$ строках задано описание знакомых работников первой компании: $k_i$ — количество знакомых $i$-го работника первой компаний, и $k_i$ чисел, каждое из которых от 1 до $m,$ — номера знакомых во второй компании. В том же формате в следующих $m$ строках задано описание знакомых работников второй компании. Номера работников из первой компаний от 1 до $n.$ В первой строке выходного файла должно быть три числа — максимальное количество рабочих, которое новое руководство может оставить, $k_1$ — сколько работников из первой компании и $k_2$ — сколько из второй. Во второй строке выведите $k_1$ чисел, номера работников которых нужно оставить из первой компании. В третьей строке выведите $k_2$ чисел, номера работников которых нужно оставить из второй компании. Если существует несколько ответов выведите любой. Вход

3 2
1 1
1 2
0
1 1
1 1

Ответ

3 2 1
1 3
2

Задача D. Уникальные числа

Вам дан массив целых чисел $A$ длины $N$ и набор из $M$ интервалов $[l, r]$ этого массива. Для каждого из интервалов вам необходимо найти количество различных чисел среди $A[l],$ $A[l + 1],$ $\ldots,$ $A[r].$ Первая строка входного файла содержит два целых числа $N$ и $M$ $(1 \le N \le 10^5,$ $1 \le M \le 10^5).$ В следующей строке находится массив $A$: $N$ целых чисел $A[i]$ $(1 \le A[i] \le 10^9).$ В каждой из следующих $M$ строк находятся по два числа $l[i]$ и $r[i]$ $(1 \le l[i] \le r[i] \le N),$ задающих концы соответствующего интервала. Выходной файл должен содержать ровно $M$ строк. $i$-я строка должна содержать количество различных чисел на интервале массива $A,$ заданном на $(i + 3)$-й строке входного файла. Вход

6 6
1000 2 3 1 1000 1000
2 3
1 2
4 6
3 6
3 5
1 3

Ответ

2
2
2
3
3
3

Задача E. Сумма

Вычислите значение выражения: $(f(L) + f(L + 1) + \ldots + f(R)) \pmod{P},$ где $f(x) = (x - A)(x - B)(x - C).$ Первая строка входного файла содержит шесть целых чисел $A,$ $B,$ $C,$ $L,$ $R,$ $P$ $(0 \le A, B, C, L, R \le 10^9,$ $1 \le P \le 10^9,$ $1 \le R - L \le 10^8).$ Выходной файл должен содержать одно число — ответ на задачу. Вход

1 2 3 1 5 10^9

Ответ

30

Задача F. Выборы

В городе есть $N$ перекрестков и $M$ улиц. С любого прекрестка можно доехать до любого другого и этот путь единственный. В городе началась борьба за выборы в мэры города. В финальную часть выборов вышли два кандидата. Агитация проходит на улицах. На каждой улице есть люди которые агитируют за конкретного кандидата. Первая строка входного файла содержит два целых числа $N$ и $M$ $(1 \le N,M \le 10^5).$ В каждой из следующих $M$ строках задаются описание улицы $a$ и $b$ — перекрестки, которые соединеняет это улица $(1 \le a, b \le N).$ В следующей строке задается $K$ — количество запросов $(1 \le K \le 10^5).$ В следующих $K$ строках задаются запросы. Подаются запросы двух видов:
$+$ $x$ $y$ — кандитат $x$ изменил мнение улицы $y$, и теперь улица $y$ агитируют за него $(1 \le x \le 2, 1 \le y \le M).$
$q$ $x$ $y$ $k$ — Выведите сколько улиц агитирует за кандидата $k$ между перекрестками $x$ и $y$ $(1 \le k \le 2).$ Изначально все улицы агитируют за кандидата 1. Для каждого запроса второго типа (описанного вверху) выведите ответ. Вход

3 2
1 2
1 3
3
q 1 3 1
+ 2 1
q 1 3 1

Ответ

2
1

Задача G. Факториал

Вычислите $N!$ по модулю $P$. $N! = 1 \cdot 2 \cdot \ldots \cdot N.$ В первой строке входного файла задаются $N$ и $P$ $(1 \le N \le 10^6,$ $1 \le P \le 10^9).$ Выведите одно число — ответ к задаче. Вход

3 5

Ответ

1

Задача H. Мотивированная змея

На доске $N \times M$ в клетке $(1, 1)$ находится змея, которая хочет дойти до клетки $(N, M)$ максимально мотивированной для осуществления своих целей. Змея может ходить вниз, вправо и влево. Если змея пойдет в клетку $(i,j),$ то ее настроение уменьшится на величину, написанную на этой клетке. Для того, чтобы дойти максимально мотивированной змея должна выбрать такой путь, при котором ее настроение уменьшится на минимально возможную величину. Вам задано начальное настроение змеи. Найдите максимально возможное настроение, которое будет у нее в клетке $(N, M).$ В первой строке входного файла задаются $N$ и $M$ $(1 \le N,M \le 1000).$ В следующих $N$ строках задаются по $M$ положительных целых чисел, каждое из которых не больше чем $10^6$ — числа написанные на клетках. В последней строке задается $S$ — начальное настроение $(1 \le S \le 10^{18}).$ Выведите одно число — ответ к задаче. Ответ может быть отрицательным. Вход

2 2
1 1 
1 1 
100

Ответ

97