Областная олимпиада по информатике 2020 год, 9-11 классы


Задача A. Кролики

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

У Айбара есть сад, который состоит из $K$ подряд идущих грядок. В саду живут $n$ кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано $q$ запросов, которые надо обработать. Они бывают следующих типов:
  • Кролик номер $x\; (1 <= x <= n)$ перешел на одну грядку налево или направо. При этом гарантируется, что кролик не выйдет за пределы сада
  • Посчитать количество кроликов на отрезке от грядки $l$ до грядки $r$ $(1 <= l <= r <= K)$ включительно.
Формат входного файла
В первой строке входных данных даны два числа - $n$ и $K$. \\ Далее во второй строке указаны $n$ чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число $q$ и $q$ строк описывающих запросы. Запросы задаются в следующем формате:
  • $\texttt{L } x$ - сдвинуть кролика номер $x$ на одну грядку налево
  • $\texttt{R } x$ - сдвинуть кролика номер $x$ на одну грядку направо
  • $\texttt{G } l\; r$ - Посчитать и вывести количество кроликов на отрезке от грядки $l$ до грядки $r$ включительно.
Формат выходного файла
В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.
Система оценки
Подзадача 1 (20 баллов) — $1 <= n, K, q <= 1000$ Подзадача 2 (20 баллов) — $1 <= n, K, q <= 5 * 10^5$, отсутствуют запросы сдвига кролика Подзадача 3 (60 баллов) — $1 <= n, K, q <= 5 * 10^5$
Пример:
Вход
3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7
Ответ
1
3

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

Задача B. Перестановка

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

Постройте пилообразную циклическую перестановку $p$ длины $n$. Перестановка называется циклической тогда и только тогда, когда она состоит из единственного цикла.(То есть в графе с ребрами $i$ - $p_i$ ровно одна связанная компонента). Пилообразная перестановка - перестановка $p$, такая что её члены по очереди возрастают и убывают.($p_1 < p_2 > p_3 < p_4 ...$ или $p_1 > p_2 < p_3 > p_4 ...$)
Формат входного файла
Вам дано одно целое число $n$.
Формат выходного файла
Выведите любую подходящую перестановку.
Система оценки
Данная задача содержит ровно $10$ тестов и каждый оценивается в $10$ баллов.
  1. $n = 4$
  2. $n = 5$
  3. $n = 10$
  4. $n = 11$
  5. $n = 20$
  6. $n = 21$
  7. $n = 2019$
  8. $n = 2020$
  9. $n = 12345$
  10. $n = 123456$
Пример:
Вход
4
Ответ
3 1 4 2 

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

Задача C. From And with love

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

Абай очень любит массивы. Еще больше он любит играть с подпоследовательностями массива. Подпоследовательность — это такая последовательность массива, которая может быть получена удалением нескольких (возможно ноль) элементов из этого массива. Вам дан массив $A$ из $N$ целых чисел. Рассмотрим какую--нибудь подпоследовательность массива. Пусть битовый AND этой подпоследовательности равен $X$. Тогда подпоследовательность называется хорошей, если в ней нет элемента со значением $X$. Посчитайте количество хороших подпоследовательностей.
Формат входного файла
В первой строке дается натуральное число $N$ — размер массива $A$. В следующей строке заданы $N$ целых неотрицательных чисел — элементы массива $A$.
Формат выходного файла
Выведите одно число — количество хороших подпоследовательностей. Так как ответ может быть достаточно большим, выведите его остаток от деления на $10^9 + 7$.
Система оценки
Это задача состоит из 5 подзадач и 25 тестов, каждый тест оценивается в 4 балла:
  1. $1 <= N <= 15$, $0 <= A_i < 2^{20}$. Тесты 1 -- 3
  2. $1 <= N <= 10^5$, $0 <= A_i < 2^4$. Тесты 4 -- 7
  3. $1 <= N <= 10^5$, $0 <= A_i < 2^{10}$. Тесты 8 -- 12
  4. $1 <= N <= 10^5$, $0 <= A_i < 2^{15}$. Тесты 13 -- 18
  5. $1 <= N <= 10^6$, $0 <= A_i < 2^{20}$. Тесты 19 -- 25
Пример:
Вход
5
0 2 5 3 7
Ответ
6
Замечание
Одной из хороших подпоследовательностей является 2, 5, 7. Ее битовый AND равен 0, при этом число 0 не присутствует среди 2, 5, 7. Операция побитового AND существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string&$>>, в Pascal — как <>. Таблица для побитового AND.\\ 1 $and$ 1 = 1, 1 $and$ 0 = 0\\ 0 $and$ 1 = 0, 0 $and$ 0 = 0\\

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

Задача D. Разделение массива

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

У Тимы есть три младших брата: Батыр, Димаш и Есмахан. Тима решил дать им массив $a$ из $n$ целых чисел, чтобы развлечь их. Он хочет разделить массив на три непустых частей и раздать своим братьям, чтобы каждое число было ровно в одной части. Все числа одной части должны идти подряд в массиве. Пусть $A$ - сумма чисел в первой части, $B$ - сумма чисел во второй, $C$ - сумма в третьей. Чтобы братья не ругались, Тима хочет минимизировать max(A, B, C) - min(A, B, C). Найдите минимальное значение max(A, B, C) - min(A, B, C).
Формат входного файла
В первой строке дано одно целое число $n$ $(3 <= n <= 3 * 10^5)$. Во второй строке дано $n$ целых чисел $a_1$, $a_2$, $\dots$, $a_n$ $(0 <= a_i <= 10^5)$.
Формат выходного файла
Выведите одно целое число — ответ на задачу.
Система оценки
Это задача состоит из 4 подзадач и 20 тестов, каждый тест оценивается в 5 баллов:
  1. $n <= 10^2$. Тесты 1 -- 4
  2. $n <= 5 * 10^3$. Тесты 5 -- 8
  3. $a_i <= 1$. Тесты 9 -- 12
  4. $n <= 3 * 10^5$. Тесты 13 -- 20
Пример:
Вход
7
4 1 2 3 1 3 2
Ответ
1
Замечание
Один из вариантов разделении в примере: 4 1 | 2 3 1 | 3 2 Также можно разделить 4 1 | 2 3 | 1 3 2

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

Задача E. Есмахан и стартап

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

Есмахан - начал стартап по разведению моржов. Он нанял $n-1$ работника. Есмахан - сотрудник номер $1$, все остальные пронумерованы от $2$ до $n$. У каждого из работников есть один непосредственный начальник $p_i$. У Есмахан нет начальников. Гарантируется, что значения $p_i$ образуют дерево. Теперь Есмахан должен им заплатить. Работник с номером $i$ хочет получить $a_i$ тенге. Пусть $i$ работник получит $b_i$ тенге, тогда его недовольство будет $|a_i - b_i|$. У Есмахана есть принцип - каждый работник должен получить больше чем любой его подчиненный. Вам нужно распределить зарплаты так чтобы суммарное недовольство было минимально.
Формат входного файла
В первой строке одно целое число $n$ $(1 <= n <= 200000)$. Во второй строке $n - 1$ целых чисел $p_2, p_3, ... p_n$ $(1 <= p_i <= i - 1)$ - номера начальников работников. В третей строке $n$ целых чисел $a_1, a_2, ... a_n$ $(1 <= a_i <= 10^9)$ - ожидания работников.
Формат выходного файла
Выведите одно целое число - минимальное суммарное недовольство работников.
Система оценки
Данная задача содержит ровно $25$ тестов и каждый оценивается в $4$ баллов.
  1. Тест из условия.
  2. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$, у каждого работника не больше одного подчиненного | 2 теста.
  3. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$ | 2 теста.
  4. $1 <= n <= 1000$, у каждого работника не больше одного подчиненного | 2 теста.
  5. $1 <= n <= 1000$ | 3 теста.
  6. $1 <= n <= 200000$, у каждого работника не больше одного подчиненного | 5 тестов.
  7. $1 <= n <= 200000$ | 10 тестов.
Пример:
Вход
7
1 2 1 1 5 6
1 2 3 1 4 3 3
Ответ
7
Замечание
Ответ в примере $b={5, 4, 3, 1, 4, 3, 2}$

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

Задача F. K-sort

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

У Есмахана есть массив $A$ состоящий из $N$ целых чисел $A_0,A_1,..,A_{N-1}$. Массив называется $k$-сортируемым, если массив можно отсортировать по неубыванию c помощью нескольких(возможно ноль) таких операции: выбрать индекс $i(0 <= i < N)$ и поменять местами $i$-й и $((i + k)$ mod $N$)-й элементы массива. Операция $a$ mod $b$ означает остаток $a$ при делении на $b$. Например, $7$ mod $3$ = 1, $8$ mod $4$ = 0, $5$ mod $11$ = 5. Массив считается отсортированным по неубыванию, если каждый элемент(кроме первого) не меньше чем предыдущий элемент. Есть $Q$ запросов, каждый запрос состоит из одного целого числа $k$. Для каждого запроса нужно определить, является ли массив $A$ $k$-сортируемым.
Формат входного файла
В первой строке находятся два целых числа $N,Q(1 <= N,Q <= 300000)$. Во второй строке находятся $N$ целых числа $A_0,A_1, ..., A_{N - 1}(1 <= A_i <= 10^9)$. В следующих $q$ строках находятся по одному целому числу $k_i(1 <= k_i <= N)$.
Формат выходного файла
В $q$ строках выведите по одному целому числу — в $i$-й строке выведите $1$, если массив $A$ является $k_i$-сортируемым, иначе выведите 0.
Система оценки
Это задача состоит из 5 подзадач и 25 тестов, каждый тест оценивается в 4 балла. В подзадачах выполняются следующие дополнительные ограничения:
  1. $1 <= N,Q <= 100$. Тесты 1 -- 4
  2. $1 <= N <= 100000, Q = 1$, $k_1 = N$. Тесты 5 -- 7
  3. $1 <= N,Q <= 2000$. Тесты 8 -- 11
  4. $1 <= N,Q <= 50000$. Тесты 12 -- 15
  5. $1 <= N,Q <= 300000$. Тесты 16 -- 25
Пример:
Вход
4 4
3 2 2 4
1
3
2
4
Ответ
1
1
1
0
Замечание
Изначально $A={3,2,2,4}$, т.е $A_0 = 3, A_1 = 2, A_2 = 2, A_3 = 4$. Массив $3$-сортируемый, потому что с помощью следующих операции можно отсортировать:
  1. Выберем $i = 1$, тогда $(i + 3)$ mod $N = (1 + 3)$ mod $4 = 0$. Т.е поменяем местами $A_1$ и $A_0$. Получиться $A = {2,3,2,4}$.
  2. Выберем $i = 2$, тогда $(i + 3)$ mod $N = (2 + 3)$ mod $4 = 1$. Т.е поменяем местами $A_2$ и $A_1$. Получиться $A = {2,2,3,4}$.

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