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

Вы играете в компьютерную игру. У вас имеется $N$ магических предметов разного размера. В дорожную сумку могут поместиться только предметы суммарным размером $K$. Также вы знаете $M$ заклинаний, каждое из которых имеет определенную силу и использует определенный набор из имеющихся предметов. Отправляясь в поход, вы должны заполнить сумку предметами так, чтобы суммарная сила заклинаний, которыми вы сможете воспользоваться была максимально возможной. Первая строка входного файла содержит три целых числа $N,$ $M,$ $K$ $(1 \le N,M \le 25,$ $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 15).$ Каждая из следующих $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 500).$ В следующих $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. На Марсе

Космический корабль вошел в атмосферу Марса. Но в этот момент произошел сбои в работе этой большой махины. Корабль приземлился на поверхность планеты. Но, увы, в системе навигации произошел сбой. Единственная работающая функция dist$(x, y)$ — которая рассчитывает расстояния до космического корабля с заданной точки $(x, y).$ Из-за того, что аккумулятор тоже поврежден, эту функцию можно использовать не более 10000 раз. Помогите космонавтам и определите точное место нахождения корабля. Гарантируется, что координаты космического корабля целые и по модулю не превосходит $10^9.$ Ваша программа должна может подавать следующие запросы:
C/C++ — start(), Pascal — start — должна подаватся один раз и быть самым первым запросом.
C/C++ — dist$(x, y),$ Pascal — dist$(x, y)$ — Находить расстояния до космического корабля с заданной точки $(x, y),$ функция должна быть использована
не более, чем 10000.
C/C++ — finish$(x, y),$ Pascal — finish$(x, y)$ — должна подаватся один раз и быть последним запросом, которая сообщает точное место нахождения космического корабля — $(x, y).$
Если ваша программа на языке программирования С++ надо подключить библиотеку dist.h: #include "dist.h"
Если ваша программа на языке программирования Pascal надо подключить модуль dist: uses dist;
Не определяйте функции-процедуры start, dist и finish в вашей программе. Иначе ваша программа не скомпилируется у нас.

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

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

2 3
100 1 10000 
10000 1 1 
100

Ответ

95