Алгоритмы

Фермер Джон заметил, что имеется \(N\) (\(1\le N\le 2\cdot 10^5\)) уникальных ID-номеров и для каждого уникального ID \(d_i\) (\(0\le d_i\le 10^9\)), имеется \(n_i\) (\(1\le n_i\le 10^9\)) коров с таким ID.

Эти коровы могут коммуницировать в парах, их секретный метод шифрования имеет одно строгое правило: две коровы могут обмениваться информацией если это не одна и та же корова и сумма их ID-номеров равна или \(A\) или \(B\) (\(0\le A\le B\le 2\cdot 10^9\)). В один момент времени, корова может быть вовлечена только в одну беседу (то есть никакая корова не может быть частью более чем одной пары)

ФД хочет максимизировать количество коммуницирующих пар. Определите максимальное количество бесед, которые могут состоятся в один момент времени.

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 5\cdot 10^6\)) и пытается заставить их отсортировать неотрицательный целочисленный массив \(A\) длины \(N\), полагаясь на их лень. У него много тяжелых коробок, поэтому он выстраивает коров одну за другой, где корова \(i+1\) находится за коровой \(i\), и дает \(a_i\) коробок корове \(i\) (\(0\le a_i\)).

Коровы по своей природе ленивы, поэтому они всегда ищут способ передать свою работу кому-то другому. От коровы \(1\) до \(N-1\) по порядку каждая корова смотрит на корову позади себя. Если у коровы \(i\) строго больше коробок, чем у коровы \(i+1\), корова \(i\) считает, что это «несправедливо» и отдает одну из своих коробок корове \(i+1\). Этот процесс повторяется, пока каждая корова не будет удовлетворена.

Фермер Джон пометил количество ящиков \(b_i\), которое каждая корова \(i\) держит и создал массив \(B\) из этих величин. Если \(B = sorted(A)\) тогда ФД счастлив. К несчастью. ФД забыл все кроме \(Q\) величин массива \(A\). (\(2 \leq Q \leq \min(N, 100)\)). К счастью, эти величины включают количество ящиков, которое он собирается дать первой и последней корове. Каждое число, которое помнит ФД задано в виде \(c_i \; v_i\), представляющее, что \(a_{c_i}=v_i\). (\(1 \leq c_i \leq N\), \(1\le v_i\le 10^9\)). Определите количество различных способов, которыми могут быть заполнены пропущенные величины так чтобы ФД был счастливым. ответ выводите по модулю \(10^9+7\).

У Фермера Джона есть \(N\) \((1 \leq N \leq 10^5)\) бутылок, которые он хочет наполнить молоком. Каждая бутылка изначально содержит некоторое количество молока \(m_i\) \((0 \leq m_i \leq 10^9)\). Каждый день он берёт \(A\) \((1 \le A \le N)\) бутылок и наполняет одной единицей молока.

К несчастью, Фермер Нхой, соперник ФД по бизнесу, знает об этом процессе ФД и намерен навредить. Каждый день после того, как ФД заполнит свои \(A\) бутылок, ФН незаметно крадёт одну единицу молока из \(B\) \((0 \le B < A)\) различных непустых бутылок. Чтобы оставаться незамеченным, ФН выбирает \(B\) так, чтобы оно было строго меньше чем \(A\).

После \(D\) (\(1 \leq D \leq 10^9\)) дней ФД продаёт своё молоко. Если в бутылке \(M\) единиц молока, он продаёт эту бутылку за \(M^2\) денежных единиц.

Пусть \(P\) - уникальная прибыль, такая, что FJ может гарантировать, что он получит не менее \(P\) прибыли независимо от того, как ведет себя FN, а FN может гарантировать, что FJ получит не более \(P\) прибыли независимо от того, как ведет себя FJ. Выведите значение \(P\) по модулю \(10^9+7\).

Вам дана длинная строка \(S\) из символов M и O и целое число \(K \geq 1\). Посчитайте количество способов разбить \(S\) на подпоследовательности так, что каждая подпоследовательность MOOOO....O с ровно \(K\) O, по модулю \(10^9+7\).

Поскольку строка очень длинная, Вам она не дана точно. Вместо этого Вам дано целое число \(L\) (\(1 \leq L \leq 10^{18}\)), и строка \(T\) длины \(N\) (\(1 \leq N \leq 10^6\)). Строка \(S\) есть конкатенация \(L\) копий строки \(T\).

Фермер Джон выстроил коров в ряд и хочет их сфотографировать.

Каждая из \(N\) коров \((1 \le N \le 10^5)\) имеет целую высоту от \(1\) до \(N\). ФД хочет сфотографировать их в определённом порядке. Если коровы с высотами \(h_1, \dots, h_K\) стоят в ряд слева направо, он хочет, чтобы для их высот выполнялись следующие три свойства:

• Чтобы высоты коров сначала возрастали, а потом убывали. Формально, должно существовать такое целое число \(i\), что \(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
• Чтобы рядом стояли коровы с одинаковой высотой. Формально, \(h_i \neq h_{i+1}\) для \(1 \le i < K\).
• Чтобы фотография была симметричной. Формально, если \(i + j = K+1\), then \(h_i = h_j\).

ФД хочет, чтобы на фотографии было как можно больше коров. А именно, ФД может удалить некоторых коров и переупорядочить оставшихся коров. Вычислите максимальное количество коров, которые ФД может выставить на своей фотографии, удовлетворив указанные свойства.

Беси анализирует строку из \(N\) (\(3 \leq N \leq 10^5\)) маленьких латинских букв \(s_1s_2 \ldots s_N\). Эльза рассматривает строку \(t\), содержащую три символа как MOO если \(t_2 = t_3\) и \(t_2 \neq t_1\).

Триплет \((i, j, k)\) валидный, если \(i < j < k\) и строка \(s_i s_j s_k\) формирует MOO. Для этого триплета ФД выполняет следующее, чтобы вычислить его величину

• ФД сгибает строку \(s\) на 90-градусов в индексе \(j\)
• Величина триплета - удвоенная площадь \(\Delta ijk\).

Другими словами, величина триплета есть \((j-i)(k-j)\).

Беси задаёт Вам \(Q\) (\(1 \leq Q \leq 3 \cdot 10^4\)) вопросов. В каждом вопросе она даёт Вам два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\)) и просит Вас определить максимальную величину среди всех валидных триплетов \((i, j, k)\) таких, что \(l \leq i\) и \(k \leq r\). Если валидных триплетов нет, выведите \(-1\).

Решение задачи может потребовать использовать 64-й целый тип (например, "long long" in C/C++).

Сад Беси имеет \(N\) растений, помеченных от \(1\) до \(N\) (\(2\leq N\leq 5\cdot 10^5\)) слева направо. Беси знает, что растение \(i\) требует не менее \(w_i\) (\(0\leq w_i \leq 10^6\)) единиц воды.

У Беси своеобразная ирригационная система с \(N-1\) каналами, пронумерованными от \(1\) до \(N-1\). Каждый канал \(i\) имеет ассоциированную с ним стоимость \(c_i\) (\(1\le c_i\le 10^6\)), такую что Беси может заплатить \(c_i*k\) чтобы обеспечить растение \(i\) и \(i+1\) каждое \(k\) единицами воды где \(k\) неотрицательное целое число.

Беси сильно занята и может не иметь времени использовать все каналы. Для каждого \(2\leq i \leq N\) вычислите минимальную стоимость требуемую, чтобы доставить воду растениям от \(1\) до \(i\) используя только первые \(i-1\) каналов.

**Замечание: Время на тест в этой задаче 4 сек, в 2 раза больше, чем по умолчанию.**

Беси использует свой изящный телескоп чтобы сделать фотографии всех звёзд на ночном небе. Её телескоп может сделать фото \(N \times N\) (\(1 \leq N \leq 1000\)) пикселов, где каждый пиксел это или звезда, или пустое небо. Каждая звезда будет представлена ровно одним пикселом, и никакие две звезды на разделяют один и тот же пиксел.

Ночью происходит что-то странное со звёздами на небе. Каждая звезда или исчезает или перемещается на \(A\) пикселов вправо и на \(B\) пикселов вниз (\(0 \leq A,B \leq N\)). Если звезда исчезает или перемещается за границу фото, она больше не появляется на втором фото.

Беси делает фотографии до и после перемещений, но после экспериментов, она случайно наложила одну фотографию на другую. Теперь она видит белые пикселы, которые были пустыми на обеих фотографиях, серые пикселы, где звезда была ровно на одном фото и чёрные пикселы, где была звезда на обоих фотографиях. Беси также помнит, что на второй фотографии не появились новые звёзды, поэтому первая фотография содержит все звёзды ночного неба. Если не существует исходного положения звёзд, которое может произвести финальное фото, выведите \(-1\).

Беси помогает Эльзе играть со словами. Слова берутся из банка, содержащего \(M\) различных слов, ни одно слово не является префиксом другого.

Пока банк не пустой, Беси выбирает слово из банка, удаляет его из банка, читает его Эльзе по одному символу за раз слева направо. Задача Эльзы сказать Беси, как только она уникально определит слово, после чего Беси прекращает чтение.

Беси уже решила читать слова из словаря в порядке \(w_1,w_2,\dots,w_M\). Если Эльза ответит так быстро, как это возможно, сколько символов из каждого слова прочитает Беси?

Слова заданы в сжатом формате. Сначала мы определяем \(N+1\) (\(1\le N\le 10^6\)) различных слов и затем банк слов состоит из всех этих слов, ни одно из которых не является префиксом другого. Слова определяются следующим образом:

• Изначально, 0-ое слово - пустая строка.
• Затем для каждого each \(1\le i\le N\), \(i\)-ое слово будет равно \(p_i\)-ому слову плюс дополнительный символ в конце (\(0\le p_i<i\)). Символы выбираются так, что все \(N+1\) слов различны.

Фермер Джон выстроил \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) своих коров в ряд \(a\). \(i\)'-ая корова от начала ряда \(a\) помечена целым числом \(a_i\) (\(1 \leq a_i \leq N\)). Несколько коров могут быть помечены одним и тем же числом.

ФД конструирует ряд \(b\) следующим образом:

• Изначально массив \(b\) пустой.
• Пока массив \(a\) не пустой, удалить первый элемент ряда \(a\) и добавить или не добавить этот элемент в конец массива \(b\).

ФД хочет сконструировать \(b\) так, чтобы последовательность меток в \(b\) от начала к концу была лексикографически наибольшей.

Прежде чем ФД начнёт конструировать ряд \(b\), он может выполнить следующую операцию не более чем один раз.

• Выбрать корову в ряду \(a\) и переместить её в любую позицию, кроме текущей.

При условии, что ФД оптимально выполняет эту операцию не более одного раза, выведите лексикографически наибольшую последовательность \(b\), которую он сможет получить.

Каждый тест состоит из \(T\) (\(1 \leq T \leq 100\)) независимых подтестов.

**Замечание: Время на тест для этой задачи 3сек, в 1.5 большее чем по умолчанию. Память на тест для этой задачи 512MB, в два раза больше чем по умолчанию.**

Беси проходит тест вида да/нет из \(N\) вопросов (\(1\le N\le 2\cdot 10^5\)). За \(i\)-ый вопрос она может добавить \(a_i\) баллов если ответит правильно, и отнять \(b_i\) баллов, если ответит неправильно или не изменить сумму, если не ответит вообще на вопрос (\(0<a_i,b_i\le 10^9\)).

Беси знает ответы на все вопросы, но боится, что администратор теста Эльза подменит до \(k\) вопросов так, чтоб получилось, что Беси ответила неправильно.

Заданы \(Q\) (\(1\le Q\le N+1\)) кандидатов величин \(k\) (\(0\le k\le N\)), определите количество баллов, которые Беси гарантированы для каждого \(k\), зная, что она должна ответить не менее чем на \(k\) вопросов.

У Фермера Джона есть \(N\) коров, помеченных числами от \(1\) до \(N\) (\(2\le N\le 16\)). Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если между ними есть ребро в этом графе.

За одну операцию Вы можете добавить или удалить одно ребро в этом графе. Посчитайте минимальное количество операций, которое требуется выполнить, чтобы обеспечить следующее свойство в этом графе: Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\) по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).

У Фермера Джона есть квадратный холст, представленный решёткой из \(N\) * \(N\) ячеек, (\(2 \leq N \leq 2000\), \(N\) чётное). Он рисует по следующим правилам:

1. Сначала он делит холст на четыре равных квадранта, разделённых горизонтальными и вертикальными линиями через центр холста.
2. Далее он рисует любимую картинку в правом верхнем квадранте холста. Каждая ячейка верхнего правого квадранта или закрашена (представлено символом '#') или не закрашена (представлено символом '.').
3. Наконец, гордясь своим рисунком, он отражает его через ранее указанные вертикальные и горизонтальные линии в другие квадранты холста.

Например, предположим \(N=8\) и ФД нарисовал следующую картинку в правом верхнем квадранте на шаге 2:

.#..
.#..
.##.
....

Тогда после отображения через горизонтальные и вертикальные линии в другие квадранты на шаге 3, холст будет выглядеть так:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Однако, пока ФД спал, Беси пробралась в его амбар и украла холст. А затем занялась вандализмом: Она стерла некоторые ячейки и закрасила некоторые другие ячейки. После чего вернула холст ФД.

ФД хочет модифицировать холст так, чтобы он снова удовлетворял условиям отражения, то есть результату отражения правого верхнего квадранта во все остальные квадранты. Поскольку он имеет ограниченное количество ресурсов, он хочет получить результат минимальным количеством операций, закрашивания или стирания одной ячейки.

Вам задан холст после вандализма Беси, а также последовательность \(U\) (\(0\le U \leq 10^5\)) модификаций холста, каждое переключает ячейку в '.', если в ней была '#' и наоборот. Прежде каждого обновления и после каждого обновления выведите минимальное количество операций \(x\), которое требуется выполнить, чтобы отражение было удовлетворено.

ПР�МЕР ВВОДА:

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

ПР�МЕР ВЫВОДА:

4
3
2
1
0
1

Следующий холст удовлетворяет условию отражения и отличается от оригинального холста на 4 операции:

....
####
####
....

Невозможно сделать исходный холст удовлетворяющим условию отражения испольуя менее чем 4 операции.

После обновления \((1, 3)\), холст выглядит так:

....
##.#
####
..##

Требуется 3 операции, чтобы холст стал удовлетворять условию отражения.

После обновления \((2, 3)\), холст выглядит так:

....
####
####
..##

Требуется 2 операции, чтобы сделать холст удовлетворяющим условию отражения.

Автор: Chongtian Ma

Беси учиться кодировать на простом языке программирования. Она сначала написала корректную программу, а затем выполнила её, получив некоторую выходную последовательность.

Определение:

• программа это непустая последовательность операторов.
• Оператор имеет форму "PRINT \(c\)" где \(c\) - целое число, или "REP \(o\)", за которым следует программа, за которой следует "END", где \(o\) - целое число не менее 1.

• Выполнение программы исполняет операторы последовательности.
• Выполнение оператора "PRINT \(c\)" добавляет \(c\) в выходную последовательность.
• Выполнение оператора, начинающегося с "REP \(o\)" выполняет внутреннюю программу \(o\) раз

Пример программы Беси.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

Эта программа выведет последовательность \([1,2,2,1,2,2,1,2,2]\).

Беси хочет вывести последовательность \(N\) (\(1 \le N \le 100\)) положительных целых чисел. Эльза предложила Беси использовать не более \(K\) (\(1 \le K \le 3\)) операторов "PRINT". Заметим, что Беси может использовать сколько хочет операторов "REP". Также заметим, что каждое положительное число в последовательности не более \(K\).

Для каждого \(T\) (\(1 \le T \le 100\)) независимого подтеста определите, может ли Беси написать программу, которая выведет некоторую заданную последовательность, используя не более \(K\) операторов "PRINT".

Вам дан массив \(a\) из \(N\) неотрицательных чисел \(a_1, a_2, \dots, a_N\) (\(1\le N\le 2\cdot 10^5, 0\le a_i\le N\)). За одну операцию Вы можете изменить любой элемент \(a\) на любое неотрицательное число.

mex массива это минимальное неотрицательное число, которого нет в массиве. Для каждого \(i\) в интервале от \(0\) до \(N\) включительно, вычислите минимальное количество операций, которое Вы должны сделать, чтобы сделать mex массива \(a\) равным \(i\).

Беси ищет новую работу. К счастью сейчас \(K\) фермеров проводят интервью для найма работников. Поскольку желающих найти работу много, фермеры решили перенумеровать коров и интервьюировать их в порядке нумерации. \(N\) коров подали заявки на интервью, поэтому у Беси номер \(N+1\) (\(1 \leq K \leq N \leq 3 \cdot 10^5\)).

Процесс интервью проходит следующим образом. В момент времени \(0\) фермер \(i\) начинает интервью с коровой \(i\) для каждого \(1 \leq i \leq K\). После того, фермер заканчивает интервью он немедленно начинает интервьюировать следующую корову по порядку. Если несколько фермеров закончили интервью в одно и то же время, следующая корова может выбрать сама к какому из фермеров пойдёт на интервью.

Для каждого \(1\le i\le N\), Беси знает, что интервью коровы \(i\) займёт ровно \(t_i\) минут (\(1 \leq t_i \leq 10^9\)). Однако она не знает, какого фермера предпочтёт каждая корова.

Поскольку работа очень важна для Беси, она хочет хорошо подготовиться к интервью. Чтобы сделать это, она должна знать, когда она попадёт на интервью и к какому фермеру может потенциально попасть. Помогите найти эту информацию!

У Беси есть два массива длины \(N\) (\(1 \le N \le 500\)). \(i\)-ый элемент первого массива есть \(a_i\) (\(1 \le a_i \le 10^6\)). \(i\)-ый элемент второго массива есть \(b_i\) (\(1 \le b_i \le 10^6\)).

Беси хочет разделить два массива на не-пустые подмассивы так что будут выполняться следующие условия:

1. Каждый элемент принадлежит точно 1 подмассиву.
2. Оба массива разделены на одинаковое количество подмассивов - пусть \(k\). То есть, первый массив разделён ровно на \(k\) подмассивов. И второй массив также разделён ровно на \(k\) подмассивов.
3. Для всех \(1 \le i \le k\),, среднее \(i\)-го подмассива слева первого массива строго меньше либо равно среднему \(i\)-го подмассива слева второго массива.

Подсчитайте сколькими способами можно разделить массивы на непустые подмассивы выполнив указанные ограничения. Выводить ответ по модулю \(10^9+7\). Два способа считаются различными, если количество элементов подмассива различается или некоторый элемент принадлежит различным подмассивам.