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

У Айбара есть сад, который состоит из $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

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

Постройте пилообразную циклическую перестановку $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 

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

Абай очень любит массивы. Еще больше он любит играть с подпоследовательностями массива. Подпоследовательность — это такая последовательность массива, которая может быть получена удалением нескольких (возможно ноль) элементов из этого массива. Вам дан массив $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. Разделение массива

У Тимы есть три младших брата: Батыр, Димаш и Есмахан. Тима решил дать им массив $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. Есмахан и стартап

Есмахан - начал стартап по разведению моржов. Он нанял $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

У Есмахана есть массив $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}$.