Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

У ФД есть \(B\) пар ботинок, пронумерованных \(1 \dots B\). Некоторые из них тяжёлые, а некоторые полегче. В частности, пара \(i\) позволяет ФД ходить по снегу не более \(s_i\) футов глубины и позволяет ФД продвигаться на расстояние \(d_i\) вперёд на каждом шагу.

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

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

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

Беси, однако разрешено делать остановки для отдыха и поедания травы. Но она может их делать не везде. Имеется \(N\) мест для остановок на тропинке (\(1 \leq N \leq 10^5\)); \(i\)-ая остановка находится на \(x_i\) метров от начала тропинки (\(0 < x_i < L\)), а трава на ней имеет вкусность \(c_i\) (\(1 \leq c_i \leq 10^6\)). Если Беси остановится в месте \(i\) на \(t\) секунд, она получит \(c_i \cdot t\) вкусности травы.

Беси двигается со скоростью \(r_B\) секунд за метр (\(1 \leq r_B \leq 10^6\)). Поскольку Беси моложе, \(r_B\) строго меньше \(r_F\).

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

Помогите Беси найти максимальное суммарное значение съеденной вкусной травы которое она может получить, в уверенности, что ФД завершит подъём.

Сцена для шоу представляет \(N\) платформ, размещённых по кругу. На каждой платформе от \(1\) до \(N\) коров формируют стек (корова становится на корову). По сигналу главного на манеже, все стеки параллельно "падают" по часовой стрелке так, что нижняя корова стека не движется, корова на ней движется на одну платформу по часовой стрелке, следующая корова - на две платформы и т.д. В результате получаются новые стеки коров.

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

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

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

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

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако некоторые записи потерялись.

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

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

Фермер Джон знает время \(a_i\), в которое корова \(i\) планирует прибыть на это пастбище, а также количество времени \(t_i\), которое эта корова собирается провести на этом специальном пастбище. После того, как корова \(i\) начинает есть траву, она делает это всё время \(t_i\), в течение которого все вновь прибывшие коровы вынуждены ждать. Если несколько коров ждут, когда пастбище освободится, корова с более высоким старшинством будет следующей на поедание травы. С этой целью корова, которая прибывает прямо, когда другая корова завершает есть траву, называется "ожидающей". Аналогично, если некоторое количество коров прибывает в один и тот же момент времени, и никакая корова не ест, то корова с более высоким старшинством принимается за еду.

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

”„ е®зҐв ўлЎа вм Ї®¤¬­®¦Ґбвў® Є®а®ў, Ё § вҐ¬ Їа®ЁвҐаЁа®ў вмбп Ї® н⮬㠯®¤¬­®¦Ґбвўг, ўл§лў п Є ¦¤го Ё§ нвЁе Є®а®ў Ї® ®зҐаҐ¤Ё (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп Ёе ID), ®Їпвм Ё ®Їпвм ¤® вҐе Ї®а, Ї®Є  ўбҐ Є®а®ўл ­Ґ бв ­гв ®вб®авЁа®ў ­л. Ќ ЇаЁ¬Ґа, Ґб«Ё ®­ ўлЎҐаҐв Ї®¤¬­®¦Ґбвў® Є®а®ў б ID \(\{2, 4, 5\}\), в® ®­ б­ з «  ўл§®ўҐв Є®а®ўг \(2\), § вҐ¬ Є®а®ўг \(4\), § вҐ¬ Є®а®ўг \(5\). …б«Ё ўбҐ \(N\) Є®а®ў Ґйс ­Ґ ®вб®авЁа®ў ­л, ®­ Ўг¤Ґв ўл§лў вм нвЁе Є®а®ў ®Їпвм Ё ®Їпвм, бЄ®«мЄ® ­г¦­® а §.

”„ е®зҐв ¬Ё­Ё¬Ё§Ёа®ў вм а §¬Ґа нв®Ј® ¬­®¦Ґбвў . Ѓ®«ҐҐ в®Ј®, Ї®бЄ®«мЄг ®­ бзЁв Ґв зЁб«® \(K\) бз бв«Ёўл¬, Ї®¬®ЈЁвҐ Ґ¬г ®ЇаҐ¤Ґ«Ёвм \(K\)-®Ґ «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ё­Ё¬ «м­®Ґ Ї®¤¬­®¦Ґбвў® ¬Ё­Ё¬ «м­®Ј® а §¬Ґа  в Є®Ґ, зв® ўл§лў п Ї®б«Ґ¤®ў вҐ«м­® Є®а®ў нв®Ј® Ї®¤¬­®¦Ґбвў  ­г¦­®Ґ Є®«ЁзҐбвў® а § ¬®¦­® ®вб®авЁа®ў вм ўбҐе Є®а®ў.

Џ®¤¬­®¦Ґбвў® \(S\) Ё§ \(\{1,\dots,N\}\) ­ §лў Ґвбп «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 Ї®¤¬­®¦Ґбвў® \(T\) Ґб«Ё бЇЁб®Є н«Ґ¬Ґ­в®ў ў \(S\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, зҐ бЇЁб®Є н«Ґ¬Ґ­в®ў Ё§ \(T\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп). Ќ ЇаЁ¬Ґа, \(\{1, 3, 6\}\) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 \(\{1, 4, 5\}\).

ЋжҐ­Ёў ­ЁҐ: ‚ вҐбв е ­  \(3/16\) Ў ««®ў \(N \leq 6\) and \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(5/16\) Ў ««®ў, \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(8/16\) Ў ««®ў, ­Ґв ¤агЈЁе ®Ја ­ЁзҐ­Ё©.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4 1
4 2 1 3

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

2
1
4

Њл ­ зЁ­ Ґ¬ б ¬ ббЁў  \(\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 1Ў Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 4 Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}\). ‚ нв®© в®зЄҐ ¬ ббЁў ®вб®авЁа®ў ­.

Problem credits: Spencer Compton