Республиканская олимпиада по информатике, 2011 год, 9 класс


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

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Вы играете в компьютерную игру. У вас имеется $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. Ферзи

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

На шахматной доске $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. Слияние

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Идет слияние двух компаний. В первой $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. Уникальные числа

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Вам дан массив целых чисел $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. Сумма

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Вычислите значение выражения: $(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. Выборы

Ограничение по времени:
2 секунды
Ограничение по памяти:
64 мегабайта

В городе есть $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. Факториал

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Вычислите $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. Мотивированная змея

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

На доске $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

комментарий/решение
результаты