Информатика

Фермер Джон заметил, что имеется \(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++).

У Фермера Джона есть массив \(a\) из \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) неотрицательных целых чисел и целое число \(M\) (\(1 \leq M \leq 10^9\)). Затем ФД спрашивает у Беси число \(x\). За одну операцию ФД может выбрать индекс \(i\) и вычесть или прибавить \(1\) к \(a_i\). ФД называет число скучным - если оно равно минимальному количеству операций, которые он должен выполнить, чтобы \(a_i-x\) стало делится на \(M\) для всех \(1 \leq i \leq N\).

Среди всех возможных \(x\) выберите минимально возможное скучное число.

Сад Беси имеет \(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\).

**Замечание: Время на тест в этой задаче 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\) слов различны.

Беси стоит пере двумя стогами сена. Первый содержит \(a\) снопов, второй - \(b\) снопов \(1\le a,b\le 10^{18}\)).

Она должна превратить их в стоги с \(c\) и \(d\) снопами - ни больше, ни меньше.

Беси может выполнять только такие два заклинания:

• Увеличить размер первого стога РЅР° количество СЃРЅРѕРїРѕРІ РІРѕ втором стоге.
• Увеличить размер второго стога РЅР° количество СЃРЅРѕРїРѕРІ РІ первом стоге.

Для каждого из \(T\) (\(1\le T\le 10^4\)) независимых подтестов, выведите минимальное количество операций, чтобы добиться нужного результата, или если это невозможно, выведите -1.

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

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

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

-1
3
-1
0

В первом подтесте невозможно, посокльку изначально \(b>d\), разрешённые операции могут только увеличивать \(b\).

Во втором подтесте изначально стоги имеют \((5, 3)\) снопов. Беси может увеличить первый стог на количество снопов во втором получит \((8, 3)\). Затем увеличит количество второй стог на новое количество снопов в первом, получит \((8, 11)\) Затем сделает эту операцию ещё раз и получит \((8, 19)\) � это минимальное количество операций, чтобы получить данный результат.

Заметим, что в третьем подтесте ответ не такой как во втором, потому, что \(c\) и \(d\) поменяны местами (порядок куч имеет значение).

В четвертом подтесте не требуется выполнять операции.

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

1
1 1 1 1000000000000000000

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

999999999999999999

Автор: Benjamin Qi

Фермер Джон выстроил \(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\) вопросов.

Ответьте на \(Q\) (\(1\le Q\le 10^5\)) независимых запроса следующего вида:

Вам даны четыре целых числа \(a,b,c,d\) (\(-10^{18}\le a,b,c,d\le 10^{18}\)). За одну операцию Вы можете сделать либо \(a\mathrel{+}=b\), или \(b\mathrel{+}=a\) Определите минимальное количество операций чтобы трансформировать \((a,b)\) в \((c,d)\), если это невозможно сделать, выведите \(-1\).

У Фермера Джона есть двоичная строка длиной \(N\) \((1 \leq N \leq 10^9)\), изначально из одних нулей.

Сначала он выполнит \(M\) (\(1 \leq M \leq 2 \cdot 10^5\)) изменений строки по порядку. Каждое изменение переворачивает каждый символ от \(l\) до \(r\). То есть \(0\) изменяется на \(1\) и наоборот.

Затем он задаёт Вам \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) вопросов. Для каждого вопроса Вы должны ввести лексикографически наибольшую подпоследовательность длины \(k\) состоящую из символов подстроки от \(l\) до \(r\). Если Ваш ответ - двоичная строка \(s_1s_2 \dots s_k\), выведите \(\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}\) (то есть строка интерпретируется как двоичное число) по модулю \(10^9+7\).

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

Напомним, что строка \(A\) лексикографически больше чем строка \(B\) такой же длины если и только если в первой позиции \(i\), если она существует, \(A_i \neq B_i\), выполняется \(A_i > B_i\).

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

5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 1

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

21
13
7
3
1
5
5
3
1

После выполнения \(M\) операций, строка такова: \(10101\).

Для первого запроса - длины \(5\) ответ вся строка \(10101\), которая интерпретируется как \(1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21\).

Для второго запроса, существует \(5\) уникальных подпоследовательностей длины \(4\): \(0101\), \(1101\), \(1001\), \(1011\), \(1010\). Лексикографически наибольшая из них \(1101\), которая интерпретируется как \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13\).

Для третьей строки лексикографически наибольшая последовательность \(111\), которая интерпретируется как \(7\).

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

9 1 1
7 9
1 8 8

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

3

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

30 1 1
1 30
1 30 30

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

73741816

Не забудьте выводить ответ по модулю \(10^9+7\).

Автор: Chongtian Ma

У Фермера Джона есть \(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".