Алгоритмы

Беси знает \(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\).

В сарае ФД есть четыре ведра, каждое хранит семена своего типа. ФД хочет посадить на каждом пастбище траву семенами одного из этих типов. ФД хочет каждой их своей коров различную диету. Каждая из его \(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

\(M\) друзей ФД (\(1 \leq M \leq 10^5\)) часто его посещают. Во время визита друга \(i\), ФД вместе с ним путешествует по уникальному пути от фермы \(A_i\) до фермы \(B_i\) (возможно \(A_i = B_i\)). Дополнительно, они пробуют молоко каждой коровы на своём пути. Поскольку друзья ФД также фермеры, они имеют сильное предпочтение по молоку. Каждый из них пьёт молоко только определённого типа коров. Любой из друзей ФД будет счастливым, только если сможет попить свой предпочитаемый тип молока во время пути.

Определите для каждого друга, будет ли он счастливым.

Вдоль дороги имеется \(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\).

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

Чтобы улучшить свои фигуры коровы занялись гимнастикой. Фермер Джон назначил любимую корову Бесси тренером для \(N\) других коров. В каждом из \(K\) практических занятий (\(1 \leq K \leq 10\)), Бесси ранжирует \(N\) коров в соответствии с их результатами (\(1 \leq N \leq 20\)).

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

Помогите Бесси вычислить количество состоятельных пар.

Её любимый алгоритм - пузырьковая сортировка. Ниже приведена его реализация в коровьем коде, которая сортирует массив \(A\) длины \(N\).

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

По данному массиву предскажите, сколько раз будет напечатано слово "moo" этим кодом Беси.

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

Назовём позицию между элементами \(i\) и \(i+1\) массива \(A\) точкой разбиения если максимум из \(A[...i]\) не больше чем минимум \(A[i+1 \ldots]\). Беси помнит, что быстрая сортировка реорганизует массив так, чтобы у него появилась точка разбиения, а затем рекурсивно сортирует две стороны \(A[...i]\) и \(A[i+1 \ldots]\). Однако хотя она помнит, что все точки разбиения можно найти за линейное время, она забыла как в быстрой сортировке реорганизуется массив, чтобы быстро создать точку разбиения. Она решила использовать пузырьковую сортировку для решения этой задачи

Ниже приведен алгоритм Беси Сначала она написала простую функцию, которая делает один проход пузырьковой сортировки:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Рекурсивный код Беси для "быстрой" сортировки такой:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A) 
   divide A at all partition points; recursively quickish_sort each piece
}

Теперь Беси интересно, насколько быстро работает её код. Для простоты она считает, что её итерация работает линейно и поэтому она просто инкрементирует глобальную переменную work_counter внутри цикла текущим размером массива так, чтобы оценивать общую работу, выполненную алгоритмом.

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

Однако если одну из дорожек заблокировать, то ферма разделится на две части, внутри каждой из которых связность сохранится, а между ними - нет. Поэтому ФД строит \(M\) дополнительных дорожек (\(1 \leq M \leq 50,000\)), каждая из которых имеет положительную целую длину не более \(10^9\). Коровы пользуются исходными дорожками, пока это возможно.

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

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

Её любимый алгоритм называется "пузырьковая сортировка". Ниже приведена начальная его версия в коровьем коде для сортировки массива \(A\) из \(N\) элементов.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

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

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

По заданному входному массиву предскажите, сколько раз слово "moo" будет напечатано этим модифицированным кодом.

1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой, затем корову 2 и затем корову 5.

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

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

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

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(t = 1,000,000,000\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

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