Aidos Nurmash


Задача №1. 

Задача B. Охрана природы

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

Темирулан — активист охраны природы и защиты животных округа Каспий. Недавно во время прогулки по родному краю он обнаружил редкое растения типа ЖранУ. Растения ЖранУ являются особенными. Они растут только в тени под большими, старыми деревьями. Темирулан проверил $n$ подряд идущих деревьев, и для каждого из них узнал можно ли под ним посадить растение ЖранУ. Темирулану растение ЖранУ сильно понравилось, и он решил, что каждый год в течении следующих $q$ лет будет делать посадку этого растение. При посадке растения он выбирает некоторое количество подряд идущих деревьев от $l$ до $r$, и под каждым деревом делает посадку растение ЖранУ если можно посадить. После посадки растения их обязательно нужно полить, каждый год Темирулан поливает все растения посаженные в этот год. Для поливки растения Темирулан взял с собой ведро размера $k$, которым можно полить все растения ЖранУ которые растут под $k$ подряд идущими деревьями. Темирулан хочет полить каждое посаженное растение хотя бы один раз. Какое минимальное количество ведер воды для поливки всех новых посаженных растении? Обратите внимание, каждый год Темирулан поливает растения не учитывая предыдущий год.
Формат входного файла
Первая строка входных данных содержит два целых числа $n$ и $t$ $(1 \le n \le 2\cdot10^5, 0 \le t \le 1)$ — количество деревьев и константное число для чтения входных данных. Далее следующие $n$ чисел описывает $i$-е дерево — если $i$-е число 0, то нельзя посадить растение под $i$-м деревом, иначе можно. Деревья нумеруются с нуля. В следующей строке число $q$ $(1 \le q \le 2\cdot10^5)$ — количество посадок растений. Затем в следующих $q$ строках даны по три целых числа: $a_i$ $b_i$ $c_i$ $(0 \le a_i, b_i, c_i \le 10^9)$ Обратите внимание, что концы отрезков $[l_i, r_i]$ и число $k_i$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: { \center $l_i = (a_i \oplus (t*lastans)) \mod n, \quad r_i = (b_i \oplus (t*lastans)) \mod n, \quad k_i = ((c_i \oplus (t*lastans)) \mod n) +1 $ \center
} где $lastans$ — последний ответ на запрос (изначально $lastans$ равен $0$). Если значение $l_i$ получилось больше значения $r_i$, то нужно поменять местами значения $l_i$ и $r_i$. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$.
Формат выходного файла
Выведите $q$ строк. В $i$-й строке выведите одно число — ответ для $i$-го запроса.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. $n \le 100$, $k_i = 1$, $t = 0$. Оценивается в $7$ баллов.
  2. $n \le 2000$, $q \le 2000$. Оценивается в $12$ баллов.
  3. $n \le 10^5$, $q \le 10^5$, $k_i \le 10$, $t = 0$ . Оценивается в $21$ баллов.
  4. $n \le 2\cdot10^5$, $q \le 2\cdot10^5$, $t = 0$ . Оценивается в $23$ баллов.
  5. Ограничения из условия задачи. Оценивается в $37$ баллов.
Пример:
Вход
7 0
0 1 1 0 1 1 0
6
0 2 1
0 6 0
0 6 1
1 4 2
0 6 5
1 5 5
Ответ
1
4
2
2
1
1
( Aidos Nurmash )
комментарий/решение олимпиада
Задача №2. 

Задача C. Претенденты на ГОИ

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

Каждые четыре года среди всех стран проводится <<Гладиаторская Олимпиада по Информатике>>. Это уникальное в своем роде соревнование, в котором участникам нужно иметь не только силу, но и высокий интеллект. В Берляндии сейчас приятная головная боль, в стране $N$ различных претендентов на Олимпиаду. Уровень каждого претендента обозначается числом, $i$-й претендент имеет уровень $i$. Берляндии как сильной в информатике стране разрешено отправлять любое количество участников на Олимпиаду, но в стране все равно планируют провести отбор. На отборочный раунд выбирается некоторое ненулевое количество претендентов, затем проводят $M$ туров. Далее в $i$-м туре проделываются следующие операции:
  1. Если количество оставшихся претендентов хотя бы $a_i$, то список претендентов покидают $a_i$ претендентов с минимальным уровнем. Далее заново повторяется $i$-й тур.
  2. Если количество оставшихся претендентов строго меньше чем $a_i$, то переходится к следующему туру. За исключением случая когда $i=M$, в этом случае отбор завершается.
Заметим тот факт, что после выбора претендентов на отборочные туры финальный список оставшихся претендентов определяется однозначно. Журналисты решили заранее описать всевозможные случаи и посчитать общее количество оставшихся претендентов по всем возможным изначальным выборкам претендентов. Так как это значение может быть большим выведите остаток по модулю $P$.
Формат входного файла
В первой строке входных данных даны три целых числа $M$, $N$ и $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — количество раундов, количество претендентов и число по которому надо взять остаток. Заметим, что $P$ необязательно простое число. В следующей строке даны $M$ целых чисел $a_i$ ($1 \le a_i \le 1000$) — число для $i$-го раунда.
Формат выходного файла
Выведите одно целое число — ответ на задачу.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. $n \le 18$. Оценивается в $10$ баллов.
  2. $n \le 1000$. Оценивается в $18$ баллов.
  3. $n \le 10^6$, $P = 999999937$. Оценивается в $21$ баллов.
  4. Только ограничения из условия. Оценивается в $51$ баллов.
Пример:
Вход
3 4 100000
7 3 4
Ответ
17
( Aidos Nurmash )
комментарий/решение олимпиада
Задача №3. 

Задача D. Красивая последовательность

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

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Вам даны две последовательности целых неотрицательных чисел размера $n$: $a_1, a_2, \ldots, a_n$ и размера $m$: $b_1, b_2, \ldots, b_m$. Назовем последовательность из $k$ целых чисел $c_1, c_2, \ldots, c_k$ красивой, если выполняются следующие условия: Найдите максимальную длину красивой последовательности и количество различных красивых последовательностей максимальной длины по модулю $10^9 + 9$.
Формат входного файла
В первой строке входных данных дано целое положительное число $n$ ($1 \le n \le 10^4$)~— размер последовательности $a$. Вторая строка содержит $n$ целых неотрицательных чисел $a_i$ ($1 \le a_i \le 20000$)~— последовательность $a$. В третьей строке содержится целое положительное число $m$ ($1 \le m \le 10^4$)~— размер последовательности $b$.Четвертая строка содержит $m$ целых неотрицательных чисел $b_i$ ($1 \le b_i \le 20000$)~— последовательность $b$. Числа в обеих последовательностях задаются через одиночный пробел.
Формат выходного файла
Выведите два целых числа ответ на задачу. Если ответа несуществует выведите два нуля.
Система оценки
Данная задача содержит четыре подзадачи:
  1. $1 \leq n \leq 20$, $1 \le m \le 10$. Оценивается в $9$ баллов.
  2. $1 \leq n \leq 1000$, $1 \le m \le 20$. Оценивается в $9$ баллов.
  3. $1 \leq n \leq 500$, $1 \le m \le 500$. Оценивается в $28$ баллов.
  4. $1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Оценивается в $54$ баллов.
Примеры:
Вход
1
1
1
2
Ответ
0 0
Вход
7
1 5 3 4 2 5 2
5
1 3 5 4 2
Ответ
3 6
Вход
4
1 1 3 2
4
1 3 2 2
Ответ
3 1
( Aidos Nurmash )
комментарий/решение олимпиада