Информатика

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

Беси хочет вычислить сумму сложностей во всем \(2^N\) подмножествам заданного множества из \(N\) отрезков по модулю \(10^9+7\).

Помогите Беси!

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

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

Каждый час корова или

• Останавливается, если трава в текущей ячейке уже съедена другой коровой.
• Съедает всю траву в текущей ячейке и перемещается на одну ячейку вперёд в своём исходном направлении.

Через некоторое время каждая корова оставит за собой колею пустых ячеек.

Если две коровы попадут одновременно на одну и ту же ячейку с травой, они поедят вместе и продолжат движение в своих направлениях в следующий час.

ФД не любит, когда корова прекращает пастись, и он хочет узнать, кто виноват в его остановленных коровах. Если корова \(b\) остановилась в ячейке, которую съела корова \(a\), тогда он считает, что корова \(a\) остановила корову \(b\). Более того, если корова \(a\) остановила корову \(b\), а корова \(b\) остановила корову \(c\), он считает, что корова \(a\) также остановила корову \(c\) (то есть отношение "остановила" транзитивно). Каждая корова "виновата" в количестве коров, которые она остановила. Для каждой коровы вычислите количество остановленных ею коров.

Чтобы было понятнее относительно направлений и координат, если корова в ячейке \((x,y)\) и двигается на север, то она попадёт в ячейку \((x,y+1)\), а если на восток - то в ячейку \((x+1, y)\).

ФД начинает с одного генома и редактирует его, выполняя следующие шаги:

1. Разделяет геном между каждыми двумя последовательными равными символами.
2. Реверсирует каждую из полученных подстрок.
3. Конкатенирует реверсированные подстроки в том же порядке.

Например, если ФД начинает с генома AGGCTTT, то он выполнит следующие шаги:

1. Разделит между последовательными равными символами G и T получит AG | GCT | T | T.
2. Реверсирует каждую подстроку, получит GA | TCG | T | T.
3. Конкатенирует реверсированные подстроки, получит GATCGTT.

К несчастью, после редактирования генома компьютер ФД сломался, и ФД потерял последовательность генома, с которого он начинал. Более того, некоторые части отредактированного генома повредились, заменившись на знак '?'.

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

У Элзи есть три положительных целых числа \(A\), \(B\), \(C\) (\(A\le B\le C\)). Эти целые числа предполагаются как секретные, поэтому она не говорит их своей сестре Беси. Вместо этого, она говорит Беси семь необязательно различных целых чисел в интервале \(1 \ldots 10^9\), подсказывая, что они есть \(A\), \(B\), \(C\), \(A+B\), \(B+C\), \(C+A\), \(A+B+C\) в некотором порядке.

По заданному списку из этих 7 чисел, помогите Беси определить \(A\), \(B\), \(C\). Можно доказать, что ответ уникален.

Как подающий надежды фотограф, Беси решила сделать несколько фото этих цветков. В частности, для каждой пары цветков \((i,j)\) где \(1\le i\le j\le N\), Беси делает фото всех цветков от \(i\) до \(j\) (включая \(i\) и \(j\)).

Затем Беси посмотрела на эти фотки и заметила, что некоторые фото имеют "средний цветок" - цветок, который имеет \(P\) лепестков, где \(P\) - точное среднее число лепестков среди всех цветков на этом фото.

Сколько из фотографий Беси имеют "средний цветок"?

На этот раз он делает фото с воздуха. Он хочет, чтоб все его коровы смотрели в одну сторону. Сейчас коровы организованы в решётку \(N \times N\), (\(2 \leq N \leq 1000\)) внутри квадратного пастбища, как показано ниже:

RLR
RRL
LLR

Здесь 'R' означает, что корова смотри вправо, 'L' означает, что корова смотрит влево. Поскольку коровы находятся в стаде, ФД не может говорить повернуться одной корове. Всё что он может - это повернуть целую строку или целый столбец повернув коров 'L' на 'R' или 'R' на 'L' внутри этой строки/столбца. ФД может поворачивать столбцы и строки сколько угодно раз, в том числе и поворачивать один тот же столбец или строку более чем один раз.

Как оказалось, ФД не может перевернуть всех коров в одном направлении, Но может всех коров кроме одной - определите эту корову.

Каждая корова расположена в точке \((x,y)\) на двумерной карте фермы. И нам известны \(M\) (\((1 \leq M < 10^5)\)) пар коров, принадлежащих к одной и той же группе.

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

Беси рассматривает решётку \(N \times N\) ячеек, где каждая ячейка имеет высоту. Каждая ячейка вне этой решётки считается имеющей бесконечную высоту.

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

Более формально:

• Множество ячеек называется "смежными с торцевой", если можно достичь любую ячейку этого множества из любой двигаясь вправо, влево, вверх, вниз.
• Множество ячеек называется "точечно-смежным" если можно из любой ячейки множества достичь любой другой ячейки множества, двигаясь, влево, вправо, вверх, вниз или по диагонали.
• Регион - это непустое множество ячеек "смежных с торцевой".
• Регион называется дырявым, если дополнение региона (которое включает бесконечные ячейки вне решётки) не является "точечно-смежным".
• Граница региона - это множество ячеек, ортогонально соседних (вверх, вниз, влево, вправо) к некоторой ячейке региона, но не принадлежащих региону.
• "Долина" это любой недырявый регион, в котором каждая ячейка имеет высоту ниже чем каждая ячейка границы долины.

Цель Беси - определить сумму размеров всех долин.

oo.
ooo
..o

oo.
oo.
..o

ooo
o..
o..

ooo
o.o
ooo

ooo
o.o
oo.

Беси способна разблокировать любое подмножество проходов, но имеется стоимость разблокировки каждого прохода. Чтобы сбежать, коровам достаточно собраться в одной ячейке. Бесси хочет минимизировать стоимость открытия проходов для сбора в одной ячейке.

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

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

Ферма описывается решёткой \(10 \times 10\) символов:

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

Символ 'B' представляет амбар, который горит. Символ 'L' представляет озеро, символ 'R' представляет огромную скалу.

Коровы хотят сформировать "ведерную бригаду", разместившись вдоль пути между озером и амбаром так, чтобы они могли передавать друг другу воду для тушения пожара. Ведро может передаваться между коровами, если они являются непосредственными соседями в направлении "север", "юг", "запад", "восток". Аналогично корова может набирать воду из озера, если она аналогично соседствует с ним. Наконец корова может поливать амбар из ведра, только если она аналогично непосредственно соседствует с ним.

Помогите определить минимальное количество квадратов '.', которые должны быть заняты коровами, чтобы сформировать успешную "ведерную бригаду".

Корова не может находится в квадрате, содержащем скалу, амбар или озеро. Гарантируется, что они не будут соседними друг другу.

Беси хочет посчитать все горы, но, поскольку все они примерно одного цвета, она не может увидеть гору, если её пик лежит на границе или внутри другой горы.

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

Бовинополис состоит из ряда из \(N\) пастбищ (\(1 \leq N \leq 3 \cdot 10^5\)), Каждое из которых содержит одну корову типа Holstein или Guernsey.

Правительство Бовинополиса хочет разделить его на некоторое количество непрерывных районов так, чтобы каждый район содержал не более \(K\) пастбищ (\(1 \leq K \leq N\)), и каждое пастбище содержится ровно в одном районе. Поскольку сейчас правительство контролируется Holstein-ами, они хотят найти такой способ разделения на районы, который минимизирует количество районов, в которых коров Guernsey будет больше, чем коров Holstein или столько же сколько Holstein.

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

Ферма состоит из \(N\) полей (\(1 \leq N \leq 2 \cdot 10^5\)), последовательно пронумерованных \(1 \ldots N\), и удобно соединённых множеством из \(M\) двунаправленных тропинок (\(1 \leq M \leq 2 \cdot 10^5\)). Будучи "существами привычки" коровы используют одно множество из \(N-1\) тропинок для всех своих ежедневных перемещений между полями. Они называют эти тропинки "стандартными" тропинками. Возможно добраться от любого поля до любого другого поля, используя только стандартные тропинки.

Беси, желая разнообразить маршрут своей утренней пробежки, хочет включить в маршрут нестандартные тропинки, однако не слишком много. Она определила хороший маршрут как сформированный из простого цикла, (возвращающего в исходное поле и не использующего никакое поле более одного раза), который содержит ровно две нестандартные тропинки.

Помогите Беси посчитать количество хороших маршрутов, которые она может использовать.

Беси знает \(N\) (\(1 \leq N \leq 5000\)) слов и хочет организовать их в поэму. Она определила длину в слогах каждого слова, кроме того она распределила их в "классы рифм". Каждое слово рифмуется только с другими словами из этого же класса рифм.

Каждая из поэм Беси включает \(M\) строк (\(1 \leq M \leq 10^5\)) и каждая строка должна состоять из \(K\) (\(1 \leq K \leq 5000\)) слогов. Более того, поэм Беси должна соответствовать специфической схеме рифм.

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

В настоящий момент коровы выстроились в линию в порядке \(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\). Он хочет переупорядочить коров так, чтобы они стали в порядке \(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.

Фермера Джона слышит только корова, которая стоит перед ним. В этот момент ФД может сказать ей перейти на \(k\) позиций назад (\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит , двигаются вперёд, освобождая место для неё, в которое она и становится.

Например, пусть \(N=4\) и коровы стоят в таком порядке

 ФД: 4, 3, 2, 1 

Единственная корова, которая слышит ФД, это корова \(4\). Если он скажет ей сдвинуться на 2 позиции, порядок станет таким:

 ФД: 3, 2, 4, 1 

Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.

Определите минимальное количество инструкций, которые должен дать ФД, чтобы отсортировать всех коров.

Сначала Беси кладёт три перевёрнутые ракушки на стол и маленький круглый камешек под одну из них. Затем Беси меняет пары ракушек, а Эльза пытается угадать где камешек.

В стандартной версии игры наблюдатель видит куда положили камушек в самом начале игры.

Однако в этой игре Эльза не видит начальное положение камушка, но она может угадывать положение камешка. Беси, зная правильный ответ, даёт Эльзе счёт в конце, равный количеству правильных угадываний Эльзой.

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

Сначала Беси задумывает некоторое животное. Затем Эльза задаёт серию вопросов, чтобы угадать, какое животное задумала Беси. На каждый вопрос Беси отвечает "Да" или "Нет". Например:

Эльза: "Животное летает?" 
Беси: "Нет" 
Эльза: "Ест траву" 
Беси: "Да" 
Эльза: "Даёт молоко?"
Беси: "Да" 
Эльза: "Делает му-у?"
Беси: "Да" 
Эльза: "Корова." 
Беси: "Точно!"

Назовём "правдоподобным множеством" множество всех всех животных, с характеристиками подходящими вопросам Эльзы. Эльза задаёт вопросы пока в "правдоподобном множестве" останется только одно животное, после чего она называет его в качестве ответа. Для каждого вопроса Эльза выбирает характеристику некоторого животного и спрашивает о ней (даже если ответ не сузит "правдоподобное множество"). Она никогда не спрашивает об одной и той же характеристике дважды.

Вам даны все животные, которых знают Беси и Эльза и их характеристики. Определите максимальное количество ответов "Да", которые может получить Эльза, прежде чем она узнает задуманное животное.

Мы можем описать эту сторону амбара как двумерную плоскость, на которой ФД красит \(N\) прямоугольников, стороны каждого из которых параллельны осям координат, и каждый из которых описывается своим левым нижним и правым верхним углами.

ФД хочет применить несколько слоёв краски к амбару, чтобы не пришлось перекрашивать в ближайшем будущем. Однако он не хочет тратить время делая лишние слои краски. Он считает \(K\) оптимальным числом слоёв краски. Помогите ФД определить, какая площадь будет покрыта ровно \(K\) слоями краски после того, как он закрасит все свои прямоугольники.

Беси решила воспользоваться им для поиска партнёра. Он создала аккаунт и получила список из \(N\) возможных соответствий (\(1\leq N \leq 10^6\)). Беси оценила, что каждый бык имеет вероятность \(p_i\) (\(0<p_i<1\)) согласиться на её приглашение на танец.

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