Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.
Она организована как подвешенное за вершину 0 дерево из \(n\) (\(1 \le n \le 20000\)) вершин, каждая из которых требует цифру от \(0\) до \(9\). Вершины пронумерованы от \(0\) до \(n - 1\).
Единственная информация, которой владеют коровы – что определённые последовательности длины \(5\) не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.
По заданным \(m\) (\(0 \le m \le 50000\)) последовательностям длины \(5\), вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.
Вы должны выводить свой ответ по модулю \(1234567\).
Первая строка ввода содержит два разделённых пробелом целых числа, \(n\) и \(m\) (\(1 \le n \le 20000, 0 \le m \le 50000\)) - количество вершин в дереве и количество запрещённых последовательностей соответственно.
В последующих \(i\) строках находится описание дерева. Строка \(i + 1\) содержит одно целое число \(p[i]\), означающее родителя вершины \(i\) в дереве (\(0 \le p[i] \lt i\)).
В последующих \(m\) строках находится описание запрещённых последовательностей. Строка \(n + i\) содержит два целых числа \(v_i\) и \(s_i\), разделенные пробелом - стартовую вершину последовательности, и строку из \(5\) цифр, которая не встретится в шифре начиная с вершины \(v_i\) если двигаться вверх по дереву (\(0 \le v_i \lt n\)) соответственно.
Гарантируется, что корень дерева находится не менее чем в 4 шагах от \(v_i\).
Выведите единственное целое число – количество неподходящих конфигураций цифр по модулю \(1234567\).
Подзадача 1 (10 баллов): \(1 \le n \le 15, 0 \le m \le 15\)
Подзадача 2 (15 баллов): \(1 \le n \le 1000, 0 \le m \le 2000\)
Подзадача 3 (20 баллов): \(1 \le n \le 1000, 0 \le m \le 50000\)
Подзадача 4 (55 баллов): \(1 \le n \le 20000, 0 \le m \le 50000\)
6 2 0 1 2 3 3 4 01234 5 91234
19
Легенда этой задачи слишком велика, чтобы она уместилась на этой странице, поэтому ее здесь не будет.
Вам дан массив \(V\) длины \(n\), и вы хотите уметь осуществлять над ним следующие операции:
1) get(\(a\), \(b\)) - узнать наибольший общий делитель чисел на отрезке от \(a\) до \(b\).
2) update(\(a\), \(b\), \(k\)) - для всех \(j\) от \(a\) до \(b\) увеличить \(j\)-е число на \(k \cdot (j - a + 1)\), т.е.
\(V_a += k\)
\(V_{a+1} += 2 \cdot k\)
...
\(V_b += (b - a + 1) \cdot k\)
Первая строка входного файла содержит два числа \(1 \le n \le 10^5\) - кол-во числе в массиве и \(1 \le q \le 10^5\) - кол-во запросов. Следующая строка содержит \(n\) чисел - массив \(V\) \(1 \le V_i \le 2 \cdot 10^8\).
Далее в \(q\) строках идет информация о запросах:
Каждый запрос get задается тремя числами 0 \(a\) \(b\)
Каждый запрос update задается четырьмя числами 1 \(a\) \(b\) \(k\) (\(1 \le k \le 2 \cdot 10^8\))
Для каждого запроса get выведите наибольший общий делитель чисел на отрезке от \(a\) до \(b\)
Подзадача 1(20 баллов) \(1 \le n \le 1000\), \(1 \le q \le 1000\)
Подзадача 2(20 баллов) нет запросов update
Подзадача 3(60 баллов) нет дополнительных ограничений
8 3 2 8 12 24 66 33 21 7 0 2 4 1 1 4 2 0 2 4
4 2
\(N\) субмарин бороздят просторы океана. Они расположены в ряд с первой по \(N\)-ю, расстояние между соседними по горизонтали \(5 км\). Они плывут в одну сторону в этом же порядке (впереди - первая) с одинаковыми постоянными скоростями, каждая на своей глубине. Каждая может послать сигнал, который получит ближайшая (по евклидову расстоянию на плоскости) из плывущих сзади, которая расположена глубже лодки, посылающей сигнал, если такая есть, и никто больше.
Происходят 2 вида событий:
"Поменять две соседних субмарины местами" - в нем указывается число \(i\) - номер одной из них, другая имеет номер \(i+1\). Действие происходит мгновенно, субмарины остаются на своих же глубинах.
"Отправить сигнал" – каждая субмарина отправляет сигнал.
Напишите программу, которая для каждого события второго типа посчитает, сколько максимум сигналов получила одна субмарина.
В первой строчке даны натуральные \(N\) и \(M\), разделённые пробелом.
Во второй строчке через пробел даны \(N\) натуральных ненулевых чисел, не превышающих \(3 000 000\) - глубины субмарин в миллиметрах порядке следования подводных лодок \(x\).
На каждой из следующих \(M\) строк дано по одному целому неотрицательному чиислу. Если это \(0\), то это действие первого типа, все издают сигнал; если это \(i>0\), то это значит, что субмарины \(i\) и \(i+1\) должны поменяться местами.
Для каждого события отправки сигналов субмаринами выведите в отдельной строке ответ – максимальное количество сигналов, которые получит одна из субмарин за это действие.
1. (20 баллов) \(1 < N\leq 1000\), \(1\leq M\leq 100\).
2. (30 баллов) \(1 < N\leq 1000000\), \(1\leq M\leq 20\).
3. (50 баллов) \(1 < N\leq 1000000\), \(1\leq M\leq 100000\).
Мы считаем субмарины точками.
Заметим, что субмарина, которая должна получить сигнал по описанию, при заданных горизонтальных расстояниях между лодками и возможными глубинами всегда не более, чем одна.
9 3 100 300 50 1000 1100 1200 500 400 600 0 1 0
2 3
Генная инженерия это весело. Ученые собрали несколько ДНК и хотят создать из них что-то новое. Каждая ДНК может быть представлена в виде последовательности оснований \(A\), \(G\), \(T\), \(C\). Обозначим за \(DNA[a:b]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и заканчивающийся в индексе \(b\), и за \(DNA[a..]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и идущий до конца последовательности. Ученые хотят производить следующие операции над последовательностью ДНК:
Исходные ДНК нумеруются от \(1\) до \(n\) где \(n\) - количество индексов. При создание новых ДНК они занимают два минимальных неиспользуемых натуральных индекса.
В первой строке содержится единственное число \(n\) (1 <= n <= 20) – количество исходных ДНК.
В последующих \(n\) строках содержится описание каждого ДНК – строка \(s_i\) состоящая из символов \(A\), \(G\), \(T\), \(C\) обозначающая \(i\)-е ДНК.
В следующей строке содержится единственное число \(q\) (1 <= q <= 30000)– количество операций, которые нужно выполнить.
В последующих \(q\) строках содержится описание операций, которые необходимо выполнить. Описание каждой операции задаётся в следующем форматe:
CROSS \(id_1\) \(id_2\) \(k_1\) \(k_2\), \(id_1\) != \(id_2\)
MUTATE \(id\) \(k\) \(m\)
COUNT \(id\) \(k_1\) \(k_2\)
\(id\) - индекс некоторого ДНК.
Длина каждой исходной ДНК не превышает 30000. Сумма длин ДНК, образованных в результате перекрестной операции, не будет превышать 2000000000. Общее количество ДНК не будет превышать 10000. Гарантируется, что все операции правильные.
Для каждой операции подсчёта выведите 4 числа: количества оснований \(A\), \(G\), \(T\), \(C\) соответсвенно в выбранном подотрезке данного ДНК.
Группа 0: Тест 1. 0 баллов
Группа 1: Тесты 2-6. 15 баллов. Дополнительные ограничения: длина любой ДНК не превосходит 1000. Для прохождения нужна группа 0
Группа 2: Тесты 7-11. 13 баллов. Дополнительные ограничения: Для всех запросов CROSS \(k_1\) = \(k_2\). Для прохождения нужна группа 1
Группа 3: Тесты 12-16. 23 балла. Дополнительные ограничения: отсутствует запрос MUTATE. Для прохождения нужна группа 1
Группа 4: Тесты 17-21. 14 баллов. Дополнительные ограничения: q <= 10000. Для прохождения нужны группы 2 и 3.
Группа 5: Тесты 22-26: 35 баллов. Дополнительных ограничений нет. Для прохождения нужна группа 4
2 CTCGC TGCGG 5 MUTATE 1 2 A COUNT 2 2 4 MUTATE 2 1 G CROSS 2 1 1 5 COUNT 4 3 6
0 2 0 1 0 2 0 2