Processing math: 55%

4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс


Задача D. Дерево невидимого Жанадиля

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

Дано связное дерево с N вершин. Невидимый Жанадиль выбирает какое-то подмножество вершин из заданного дерева, и удаляет все выбранные вершины и связанные с ними ребра из дерева. В результате получится лес из X связанных компонент, где компонента i содержит szi вершин, для 1<=i<=X. Основываясь на этом, Жанадиль считает значение F=Xi=12sz[i]. Ваша задача состоит в том чтоб посчитать и вывести сумму значений F по всем возможным подмножествам. Выведите ответ по модулю 109+7.
Формат входного файла
Первая строка содержит целое число N (1<=N<=2105) — количество вершин в дереве. Каждая из следующих N1 строк содержит два целых числа ui и vi (1<=ui<=N, 1<=vi<=N и uivi) — ребро дерева между вершинами ui и vi.
Формат выходного файла
Выведите сумму значений F по всем возможным подмножествам по модулю 109+7.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются дополнительные ограничения:
  1. 1<=N<=20. Оценивается в 8 баллов.
  2. 1<=N<=200. Оценивается в 13 баллов.
  3. 1<=N<=2000. Оценивается в 18 баллов.
  4. 1<=N<=2105, у каждой вершины не более двух соседей. Оценивается в 14 баллов.
  5. Ограничения из условия. Оценивается в 47 баллов.
Примеры:
Вход
3
1 2
2 3
Ответ
26
Вход
5
1 2
1 3
5 1
5 4
Ответ
216
Замечание
В первом примере из условия сушествует 8 различных возможных подмножеств, F приобретает значения: 0, 2, 2, 2, 4, 4, 4, 8. Сумма этих значений равна 0+23+43+8=26.

комментарий/решение Проверить мое решение

Задача E. НурлашКО

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

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа G, состоящий из n вершин, без ребер, во время игры игроки выполняют q операций. Операции бывают следующих типов:
  1. Добавить ориентированное ребро из вершины ui в вершину vi.
  2. Вывести xi, если существует ориентированный путь из вершины 1 в вершину xi, иначе 0.
Гарантируется, после операции граф останется ациклическим. Ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы.
Формат входного файла
Первая строка входных данных содержит три целых числа n, q и t (1<=n,q<=106,0<=t<=1) — количество вершин, количество операций и константное число. Каждая из следующих q строк содержит описание одного запроса.
  1. Запросы первого типа заданы в формате: 1 ai bi (0<=ai,bi<=2109).
  2. Запросы второго типа заданы в формате: 2 ai (0<=ai<=2109).
Обратите внимание, что вершины ui, vi для запросов типа 1 и вершина xi для запросов типа 2 закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1

x_i = (a_i \oplus (t*lastans)) \mod n + 1

} где lastans — последний ответ на запрос типа 2 (изначально lastans равен 0). Здесь \oplus обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как xor. Операция a \mod b означает взятие остатка от деления a на b. Гарантируется, что во входных данных присутствует хотя бы один запрос типа 2.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. Тесты из условий. Оценивается в 0 баллов.
  2. n, q <= 10^3, u_i = 1, t = 0. Оценивается в 11 баллов.
  3. n, q <= 10^3. Оценивается в 18 баллов.
  4. t = 0. Оценивается в 39 баллов.
  5. Ограничения из условия. Оценивается в 32 баллов.
Примеры:
Вход
5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3
Ответ
1
0
2
0
4
Вход
5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3
Ответ
1
0
2
0
4

комментарий/решение(4) Проверить мое решение

Задача F. Сделайте неотрицательным!

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

Тима считает массив целых чисел хорошим если все числа в массиве неотрицательные. У Тимы есть массив a состоящий из n целых чисел. Тима хочет сделать его хорошим, для этого он может делать следующую операцию:
  • выбрать три целых числа i,j, x такие, что 1 <= i,j <= n, i \ne j, 1 <= x <= 10^9 и a_i \ge x, а затем из числа a_i отнять x, а к числу a_j прибавить x. Стоимость такой операции |i - j| \cdot x тенге.
Помогите Тиме, потратив минимальное количество тенге сделать массив хорошим.
Формат входного файла
В первой строке находятся два целых числа n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1). Во второй строке находятся n целых числа a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8). Гарантируется, что можно сделать массив a хорошим.
Формат выходного файла
В первой строке выведите минимальное количество тенге, которое необходимо чтобы сделать массив хорошим. Если type = 1, во второй строке выведите одно целое число k (0 <= k <= 2 \cdot n) — количество операции. В следующих k строках выведите по три целых числа i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9) — описания операций. Вам не надо минимизировать количество операций, но нужно минимизировать количество потраченных тенге. Если type = 0, то кроме минимального количество тенге, ничего выводить не надо.
Система оценки
Задача состоит из восьми подзадач:
  1. Примеры из условия. Оценивается в 0 баллов.
  2. n <= 10, type = 0, -1 <= a_i <= 1. Оценивается в 8 баллов.
  3. n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400. Оценивается в 16 баллов.
  4. n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0. Оценивается в 12 баллов.
  5. n <= 2000, type = 0, -1 <= a_i <= 1. Оценивается в 15 баллов.
  6. n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1. Оценивается в 13 баллов.
  7. n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8. Оценивается в 15 баллов.
  8. n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8. Оценивается в 21 баллов.
Примеры:
Вход
7 0
1 1 -1 0 -1 1 1
Ответ
2
Вход
4 1
4 -2 -2 1
Ответ
5
3
1 2 2
1 3 1
4 3 1

комментарий/решение Проверить мое решение