Информатика

Напомним, подпоследовательность это подмножество \(a(i_1), a(i_2), \ldots, a(i_k)\) элементов из последовательности, где индексы \(i_1 < i_2 < \ldots < i_k\). Мы говорим, что подпоследовательность возрастающая, если \(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\).

ФД может переупорядочивать коров следующим образом выбрать любую подпоследжовательность и реверсировать её элементы

Например, если мы имееем список

1 6 2 3 4 3 5 3 4

мы можем реверсировать следующие элементы

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

получим

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

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

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

Коровы, последовательно пронумерованные \(1 \ldots N\) (\(1 \leq N \leq 100,000\)), организовали компанию в виде дерева, где корова 1 - президент (корень дерева). Каждая корова, кроме президента, имеет ровно одного менеджера (её родитель в дереве). Каждая корова \(i\) имеет различный професиональный рейтинг \(p(i)\), который описывает насколько хорошо она делает свою работу. Если корова \(i\) есть менеджер коровы \(j\), то мы говорим, что корова \(j\) подчиняется корове \(i\).

К несчастью коровы обнаружили что часто бывает так, что менеджер имеет меньший уровень профессиональности, чем некоторые из его подчинённых. В этом случае менеджер должен рассмотреть продвижение этих подчинённых. Ваша задача - помочь коровам узнать, когда это случается. Для каждой коровы \(i\) в компании вычислите количество подчинённых \(j\) таких, что \(p(j) > p(i)\).

Каждая корова должна быть назначена на работу ровно на один этаж. И на каждый этаж должна быть назначена хотя бы одна корова. \(i\)-ый этаж требует выполнения \(a_i\) единиц работы , каждая корова завершает одну единицу работы ровно за час. Поэтому если \(c\) коров работают на этаже \(i\), то они выполнят всю работу ровно за \(a_i / c\) единиц времени. Из соображений безопасности, этаж \(i\) должен быть завершён прежде чем начнётся работа на этаже \(i+1\).

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

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом много раз подряд. В действительности, она хочет переключаться между жестами не более чем \(K\) (\(0 \leq K \leq 20\)) раз за все игры. Например, если \(K=2\), она может играть "копыто" первые игры, затем переключиться на бумагу и в конце играть снова "копыто".

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

Амбар описывается решёткой \(N \times N\) (\(2 \leq N \leq 20\)) символов, некоторые из них пусты, некоторые заняты. Бесси начинает в левом нижнем углу (1,1) и должна пройти в правый верхний угол \(N,N\). Вы можете управлять ею посредством последовательности инструкций вида "вперёд", "повернись влево на 90 градусов", "повернись вправо на 90 градусов". Вы хотите задать кратчайшую последовательность, которая приведёт ее к цели. Есл инструкицю выполнить невозможно, Бесси пропускает её и переходит к следующей инструкции.

К несчастью, Бесси не знает, куда она смотрит вначале в клетку (1,2) или в клетку (2,1). Вы должны дать такую последовательность, которая приведёт её к цели кратчайшим образом вне зависимости от того, какой случай произошёл. Когда Беси достигает цели, она игнорирует остальные команды.

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

3
EHE
EEE
EEE

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

9

В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево, Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости от начальной ориентации.

Problem credits: Brian Dean

ФД хочет, чтобы фотография получилась красивее. Он считает, что корова \(i\) выглядит несбалансированно, если \(L_i\) и \(R_i\) отличаются более чем в 2 раза. Здесь \(L_i\) и \(R_i\) - количества коров, которые выше чем корова \(i\), слева и справа соответственно. То есть, корова \(i\) является несбалансированной, если большее из чисел \(L_i\) и \(R_i\) строго более чем в 2 раза больше, чем меньшее из этих двух чисел.

Вычислите сколько всего есть несбалансированных коров.

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

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

ФД назначил жестам цифры 1 2 3. Помогите ФД определить максимально возможное количество игр, в которых выиграет первая корова, при подходящем назначении цифр жестам.

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

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

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

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

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

Сумма может не поместится в 32-битное целое, Вы можете использовать 64-битное целое ("long long" в C/C++).

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

Фермер Джон начинает в позиции (\(f_x, f_y\)) и планирует сделать \(N\) шагов, каждый из которых в одном из 4 направлений: 'N' (север), 'E' (восток), 'S'(юг), 'W' запад. Беси начинает в позиции (\(b_x, b_y\)) и делает аналогичные \(M\) шагов. Эти пути могут иметь общие точки. В каждый момент времени ФД может остаться в своей текущей позиции либо сделать один шаг вперёд по своему маршруту (если ещё не достиг финальной позиции). В каждый момент времени (исключая тот момент, когда они находятся в стартовой позиции), энергия, потреблённая их радиоустройствами равна квадрату расстояния между ними.

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

Имеется \(N\) стогов сена, расположенных в различных целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлится с энергией \(R\) в позиции \(x\), это вызовет взрыв "радиусом \(R\)", что вызовет взрывы всех стогов сена в диапазоне \(x-R \ldots x+R\). Все стоги сена в этом диапазоне также одновременно взрываются с радиусом взрыва \(R-1\). Все ещё не взорванные стоги сена, попавшие в этот диапазон, снова взрываются уже с радиусом взрыва \(R-2\), и т.д.

Пожалуйста, определите минимальное количество энергии \(R\), с которым должна приземлиться корова, так что если она приземлится в оптимальном положении, то взорвутся все стоги сена на сцене.

Недавно ФД ввёл в контест 4 дивизиона сложности: Bronze, Silver, Gold, Platinum. Все новые участники начинают в дивизионе Bronze, как только они показывают на контесте совершенный результат, они переводятся в следующий дивизион. Возможно даже, что участник переводится несколько раз в течение одного контеста. ФД хранит список всех участников и их текущий дивизион. Поэтому каждый начинает со своего дивизиона в любой момент контеста.

Когда ФД публикует результаты последнего контеста, он хочет включить информацию по количествам переведенных из Bronze в Silver, из Silver в Gold, из Gold в Platinum. Однако он затрудняется считать перемещения, если они происходят в течение одного контеста. Беси поняла, что ФД может выводить количество случившихся перемещений непосредственно из количества участников в каждом уровне до и после контеста. Помогите ей выполнить эти вычисления.

Ферма представлена двумерной решёткой квадратных ячеек. AL начинает одной из этих ячеек в момент времени \(t = 0\), косит траву в этой ячейке. Поэтому изначально трава выкошена только в этой ячейке. Дальнейшие действия ФД описываются последовательностью из \(N\) предложений. Например, если первое предложение "W 10" то для моментов времени от \(t = 1\) до \(t = 10\) (то есть, следующие 10 единиц времени), ФД будет продвигаться по 1 ячейке на запад, кося траву в каждой ячейке по пути.

ФД медленно косит траву настолько, что она может успеть вырасти ещё прежде чем он закончит процесс. Любая ячейка травы, которую выкосили в момент времени \(t\) вырастет снова в момент времени \(t + x\).

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

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

\(N\) стогов сена расположены в различных целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлилась в позицию \(x\), этот стог взрывается с радиусом взрыва 1, что означает, что стоги сена, которые находятся на расстоянии 1 от этого стога, тоже взрываются - одновременно, но уже с радиусом взрыва, равным 2. На следующем шагу взрываются все в радиусе взрыва, но новые взрывы будут уже с радиусом 3. В общем случае, в момент времени \(t\) взрывается некоторое количество коров и каждый взрыв имеет радиус \(t\). Эти взрывы инициируют взрывы коров попавших в зону поражения в момент времени \(t+1\) с радиусами взрывов \(t+1\) и т.д

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

Каждая корова получает "воки-токи". Каждый "воки-токи" имеет ограниченный радиус передачи: "воки-токи" с мощностью \(P\) может передавать сигнал на расстояние не более \(P\). Заметим, что "воки-токи" однонаправленный: чтобы получить сигнал от другого "воки-токи", нужно чтобы он имел соотвествующую мощность.К счастью, коровы могут передавать по эстафете сообщения другу другу (в том числе и чужие) и поэтому нет необходимости для каждой коровы быть способной непосредственно передать сообщение каждой другой.

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