Информатика

Беси рассматривает решётку \(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\)) согласиться на её приглашение на танец.

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

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

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

Как и уже нарисованные прямоугольники, новые должны иметь положительную площадь, а координаты их углов \(x\) и \(y\) должны быть в интервале \(0 \ldots 200\).

Всего имеется \(N\) различных аттракционов (\(2 \leq N \leq 10^5\)). Определённые пары аттракционов связаны дорожками, которых всего \(N-1\) штук, таким образом, что существует единственный путь, состоящий из различных дорожек между любыми двумя аттракционами. Каждый аттракцион \(i\) имеет целую величину удовольствия \(e_i\), которая может измениться в течение дня, поскольку некоторые аттракционы более привлекательны утром, а некоторые - вечером.

Корова, которая проходит от аттракциона \(i\) до аттракциона \(j\) получает удовольствие всех аттракционов маршрута от \(i\) до \(j\). Забавно, что общее удовольствие от всего маршрута вычисляется как побитовое XOR всех удовольствий в течение маршрута, включая удовольствия в аттракционах \(i\) и \(j\).

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

В сарае ФД есть четыре ведра, каждое хранит семена своего типа. ФД хочет посадить на каждом пастбище траву семенами одного из этих типов. ФД хочет каждой их своей коров различную диету. Каждая из его \(M\) коров имеет два любимых пастбища. И он хочет гарантировать, чтобы на каждой такой паре пастбищ была засеяна трава различных типов, и тогда каждая корова сможет выбирать из двух видов травы. ФД знает, что нет пастбища, которое нравится более чем трём коровам.

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

К несчастью, ФД уронил свои датчики в молоко, и теперь они работают не очень хорошо. Вместо вывода точного значения трафика, датчик теперь выдаёт диапазон возможных значений. Например, датчик может показывать диапазон \([7, 13]\), означающий, что плотность трафика на этом участке не меньше чем 7 и не больше чем 13.

Шоссе вдоль фермы имеет протяжённость в \(N\) миль и движение происходит в одном направлении от мили 1 к миле \(N\). ФД хочет установить \(N\) датчиков, по одному на каждом одномильном сегменте шоссе. В некоторых из этих сегментов имеются пандусы для въезда, которые позволяют трафику вливаться на шоссе; в каждом из таких случаев ФД устанавливает свой датчик так, чтобы измерять (примерно) входящий трафик. В некоторых сегментах имеются пандусы для выезда, здесь ФД устанавливает датчик так, чтобы измерять выходящий трафик. Каждый сегмент содержит не более одного пандуса. Если на сегменте нет пандусов, ФД устанавливает датчик на собственно шоссе.

По заданным показаниям \(N\) датчиков, определите наиболее точно диапазоны, описывающие движение на шоссе от мили 1 к миле \(N\). Эти диапазоны должны не противоречить показаниям всех \(N\) датчиков.

ФОРМАТ ВВОДА:

4
on 1 1
none 10 14
none 11 15
off 2 3

ФОРМАТ ВЫВОДА:

10 13
8 12

В этом примере, комбинация считываний датчиков с сегментов 2 и 3 сужает интервал до \([11, 14]\), поскольку только показания в этом интервале соответствуют обоим считываниям \([10,14]\) и \([11,15]\). На миле 1 ровно значение 1 представляет входящий трафик, поэтому входящий трафик может быть в диапазоне \([10, 13]\). На миле 4 от 2 до 3 единиц потока может покинуть трафик, поэтому выходной поток после мили 4 может быть \([8,12]\).

Автор: Brian Dean

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

Имея немного более ограниченный словарный запас, версия FizzBuzz, которую играют коровы, включает в себя выражение «Moo» вместо Fizz, Buzz и FizzBuzz. Поэтому начало коровьей версии игры

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

По заданному числу \( N \) (\( 1 \ leq N \ leq 10 ^ 9 \)), определите \( N \)-ое число, которое говорят в этой игре.

Беси добавила нос к одному из снежков, поэтому он представляет собой голову этой абстрактной снежной коровы. Она обозначила это снежок числом 1. Чтобы усилить визуальный эффект, она планирует покрасить некоторые из снежков различными цветами. Цвета обозначаются числами в интервале \(1 \ldots 10^5\), и у Беси неограниченное количество красок всех цветов.

Когда Беси красит снежок в определённый цвет, все снежки в его поддереве также красятся в этот же цвет. (Снежок \(y\) находится в поддереве снежка \(x\), если \(x\) находится на пути от \(y\) к головному снежку). Занимаясь покраской, Беси обеспечивает, чтобы все цвета, которыми она красила снежки, оставались видимыми. Например, если у снежка есть цвета \([1,2,3]\) и Беси красит цветом \(4\), на снежке останутся следы цветов \([1,2,3,4]\).

После некоторого количества раскрашиваний, Беси хочет узнать, как раскрашена часть её коровы. Полнота цветов("colorfulness") снежка \(x\) равно количеству различных цветов \(c\), которыми раскрашен этот снежок \(x\). Если Беси спросит Вас о снежке \(x\), Вы должны ответить сумму полноты цветов всех снежков в поддереве \(x\).

Помогите Беси определить полноту цветов в определённые моменты времени.

1 x c

2 x

Вдоль дороги имеется \(N\) ферм (\(1 \leq N \leq 100\)). На фермах нет номеров, поэтому ФД тяжело ориентироваться. Зато на каждой ферме имеется цветной почтовый ящик со стороны дороги. поэтому ФД надеется, что если он посмотрит на цвета ближайших почтовых ящиков, он сможет однозначно определить, где он находится.

Каждый цвет почтового ящика обозначается буквой в интервале A..Z, таким образом, последовательность \(N\) почтовых ящиков вдоль дороги представляется строкой длины \(N\), содержащей символы в интервале A..Z. Некоторые почтовые ящики могут иметь одинаковые цвета. ФД хочет узнать минимальное число \(K\) такое, что если он посмотрит на любую последовательность из \(K\) последовательных ящиков, он уникально определит местоположение этой последовательности на дороге.

Например, предположим, что последовательность ящиков вдоль дороги есть 'ABCDABC'. ФД не может выбрать \(K=3\), поскольку если он увидит 'ABC', то имеется два расположения такой строки вдоль дороги. Минимальное значение \(K\), которое работает, \(K=4\), поскольку любые последовательные 4 символа уникально определяют его позицию вдоль дороги.

К несчастью, коровы довольно разборчивы и требуют, чтобы ФД доил их в порядке, который соответствует \(N\) ограничениям (\(1 \leq N \leq 7\)). Каждое из ограничений имеет вид "\(X\) must be milked beside \(Y\)" ("\(X\) необходимо подоить рядом \(Y\)"), что означает, что в порядке дойки корову \(X\) нужно доить сразу после коровы \(Y\) или непосредственно перед коровой \(Y\).

Пожалуйста, помогите ФД определить порядок дойки его коров, который удовлетворяет всем требуемым ограничениям. Гарантируется, что такое упорядочивание всегда возможно. Если возможно несколько упорядочиваний, выведите первое из них в алфавитном порядке. То есть, первая корова должна иметь наименьшее в алфавитном порядке имя из всех возможных имён, которые могут быть первыми. Среди всех упорядочиваний, начинающихся с этой же первой коровы, вторая корова должна быть наименьшей в алфавитном порядке среди всех корректных упорядочиваний и т.д.