Информатика

Чтобы улучшить свои фигуры коровы занялись гимнастикой. Фермер Джон назначил любимую корову Бесси тренером для \(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" этим кодом Беси.

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

Беси знает, что у поезда есть \(N\) вагонов(\(1 \leq N \leq 10^6\)), последовательно пронумерованных \(0 \dots N-1\). Вагон \(i\) имеет ID номер \(c_i\), написанный на нём (\(0 \le c_i \le 10^9\)). Все номера видны и утром, и вечером, поэтому номер каждого вагона можно увидеть два раза. Когда поезд едет утром, Беси видит вагоны в таком порядке \(c_0\), \(c_1\), ... \(c_{N-1}\). Когда поезд едет вечером, Беси видит их в том же порядке: \(c_0\), \(c_1\), ... \(c_{N-1}\).

Беси выбрала целое число \(K\) (\(1 \leq K \leq N\)), и она хочет определить минимальный ID-номер для каждого непрерывного множества из \(K\) вагонов. У Беси есть ноутбук, на котором она может производить вычисления. Но он довольно маленький, а её копыта - большие. Например, она не может написать все \(N+1-K\) минимумов. Беси мычит ответы, после того, как вычислит их.

Поезд скоро прибудет, Помогите Беси определить \(N + 1 - K\) минимумов когда поезд проезжает дважды, будьте уверены , что она использует свой ноутбук эффективно. Её ноутбук поделен на \(5500\) секций, последовательно пронумерованных \(0 \dots 5499\), и каждая секция имеет место, чтобы хранить ровно одно целое число из интервала \(-2^{31}\) ... \(2^{31}-1\) включительно. Изначально в каждой секции хранится число \(0\).

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

void helpBessie(int ID);

Ваша функция будет вызываться с номером проходящего вагона в качестве параметра.

Ваша реализация функции \(\texttt{helpBessie}\) должна вызывать следующие функции:

• int get(int index): получает значение целого числа, которое хранится в ноубуке беси в данной ячейке index.
• void set(int index, int value): устанавливает значение целым числом value в ячейке index
• void shoutMinimum(int output): говорит Беси промычать данное число
• int getTrainLength(): возвращает \(N\), количество вагонов поезда.
• int getWindowLength(): возвращает \(K\), длину окна.
• int getCurrentCarIndex(): возвращает индекс вагона, который сейчас проходит.
• int getCurrentPassIndex(): возвращает \(0\) если Беси наблюдает утренний поезд и \(1\), если Беси наблюдает вечерний поезд.

Чтобы помочь Вам начать писать свой код, мы даём начальные шаблоны для C/C++ и Java. Python и Pascal не поддерживаются в этой задаче.

Минимумы окон должны выводится в таком порядке, что минимум из вагонов \(0, 1, \dots, K-1\) нужно вывести раньше чем минимум вагонов \(1, 2, \dots, K\) и т.д. Но помимо этого ограничения упорядочения,Ваша функция может выводить минимумы во время любого из её вызовов, в любое время. Например, Ваша функция может не выводить ответов во время некоторых вызовов или выводить множество ответов во время других вызовов.

Беси имеет фантастическую кратковременную память, по этой причине нет ограничения на использование памяти в функции \(\texttt{helpBessie}\) кроме обычного на 256 Мбт. Однако между вагонами Беси не способна помнить ничего не содержащегося в её ноутбуке. Поэтому между вызовами функции, Ваша программа не может хранить состояния - а только использовать вызовы \(\texttt{get}\) и \(\texttt{set}\) calls.

Это означает:

Вам запрещено создавать глобальные или статические переменные. Любое решение, которое делает это будет дисквалифицировано. Тренеры вручную проанализируют решения, на это предмет. Вам также запрещено делать любые операции ввода-вывода.

Общее количество вызовов \(\texttt{set}\) плюс общее количество вызовов \(\texttt{get}\), сделанные Вашей программой должны быть ограничены \(25 \cdot 10^6\) для каждого теста.

Назовём позицию между элементами \(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.

Её любимый алгоритм называется "пузырьковая сортировка". Ниже приведена начальная его версия в коровьем коде для сортировки массива \(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" будет напечатано этим модифицированным кодом.

Недавно эти коровы познакомились с игрой "крестики-нолики", но им не понравилась игра только с двумя участниками, поэтому они придумали модификацию этой игры чтобы одновременно множество коров могли играть. Как и в стандартной игре, игра ведётся на доске \(3 \times 3\) , только вместо X и 0 каждый квадратик помечается символом \(A \ldots Z\) той коровы, которая сделала ход в данное поле.

Пример доски с такой игрой:

COW
XXO
ABC

Коровы заполнили все 9 квадратиков, теперь они не могут понять, кто же победил в этой игре. Понятно, как и в обычной игре "крестики-нолики", если одна корова заняла строку, столбец или диагональ, она выиграла. Однако поскольку игроков может быть больше двух, они решили позволять коровам формировать команды из двух коров. Команда объявляется победительницей, если строка, столбец или диагональ состоят только из символов коров одной команды.

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

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

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

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

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

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

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

В некоторых целочисленных координатах имеются двухглавые разбрызгиватели, оба разбразгивают воду и удобрения. Разбрызгиватель в координатах \((i,j)\) разбрызгивает воду на часть поля к северу и востоку от себя и разбрызгивает удобрения к югу и западу от себя. Формально, он поливает водой все вещественные координаты \((x,y)\) для которых \(N \geq x \geq i\) и \(N \geq y \geq j\), и удобряет все вещественные координаты \((x,y)\) для которых \(0 \leq x \leq i\) and \(0 \leq y \leq j\).

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

Помогите ФД определить количество прямоугольников с положительной площадью, на которых он может растить сладкую пшеницу. Поскольку число может быть очень большим, выводите его по модулю \(10^9 + 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 \leq N \leq 10^5\)), \(i\)-ая из которых описывается тремя целыми числами \(x_i\), \(y_i\), \(t_i\), указывающими, что рогатка может переместить навоз из позиции \(x_i\) в позицию \(y_i\) за \(t_i\) единиц времени.

У ФД есть \(M\) лотков с навозом для транспортировки (\(1 \leq M \leq 10^5\)). \(j\)-ый лоток нужно переместить из позиции \(a_j\) в позицию \(b_j\). Перемещение лотка с навозом на тракторе на расстояние \(d\) занимает \(d\) единиц времени. ФД надеется сократить время использованием рогаток. Время перемещения трактора без навоза не учитывается.

Для каждого из \(M\) лотков определите минимально возможное время транспортировки. при условии использования не более одной рогатки.

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