Информатика

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

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

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

Каждая из этих \(N + M\) коров получает индивидуальную оценку. Однако в текущем году финальное соревнование будет ограничено командой из \(K\) коров (\(1 \leq K \leq 10\)). Поэтому ФД и ФП отбирают по \(K\) коров. Затем они разбиваются на пары: лучшая корова ФД становится в пару с лучшей коровой ФП, вторая корова ФД, становится в пару со второй коровой ФП и т.д. ФД выиграет, если в каждой из этих пар его корова будет иметь более высокую оценку.

Помогите ФД посчитать количество различных способов которыми ФД и ФП могут отобрать своих коров так, чтобы ФД выиграл в соревновании. Точнее, каждая считается каждая различная пара (\(K\) коров от ФД, и \(K\) коров от ФП). Выведите ответ по модулю 1,000,000,009.

Треугольный лот имеет стоимость \(v\) если он содержит ровно \(v\) деревьев, внутри себя (деревья в вершинах не считаются, а на границах их и быть не может, поскольку по условиям все тройки деревьев не коллинеарны). Для каждого $v в интервале 0 \ldots N-3\(, определите сколько из его \)L$ потенциальных лотов имеют ценность \(v\).

Для своего последнего шоу, они купили огромный мощный лазер - такой большой, что они не смогли перместить его легко из того места, где он был приобретен. Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться как точки на плоскости - карте фермы ФД. В панах коров направить лазер так, чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал, чтобы направить луч в амбар.

На этой ферме есть \(N\) (\(1 \leq N \leq 100,000\)) точек изгороди, расположенных в различных точках на плоскости, (и отличающихся также от точек лазера и амбара), на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в вертикальный и наоборот.

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

ФД начинает свою прогулку в позиции Holstein 1 а заканчивает в позиции Holstein \(H\). Он хочет посетить каждую корову и для удобства ведёт чек-лист посещения коров. Он хочет посещать Holsteins и Guernseys в порядке их нумерации. В последовательности всех \(H+G\) коров, в порядке их посещения, коровы породы Holsteins \(1 \ldots H\) появятся как подпоследовательности (не обязательно непрерывные), аналогично и с коровами породы Guernseys. Другими словами, последовательность всех \(H+G\) коров будет сформирована перемешиванием списка Holsteins пронумерованных \(1 \ldots H\) и списка Guernseys, пронумерованных \(1 \ldots G\).

Когда ФД двигается от одной коровы к другой, преодолевая расстояние \(D\), он тратит \(D^2\) энергии. Помогите ему определить, минимальное количество энергии, требуемое чтобы посетить всех его коров в соответствии с правилами, описанными выше.

Когда дощечки лежат на земле, видно \(N\) слов. Переворачивая таблички можно получать различные множества из \(N\) слов. Чтобы помочь коровам запомнить буквы, ФД хочет подготовить некоторое количество деревянных блоков, на каждом из которых выписана одна буква алфавита. Он хочет подготовить достаточное количество блоков с каждой буквой, для того чтобы вне зависимости от того, какое множество из \(N\) слов показывается, коровы могли составить все слова используя эти блоки. Например, если \(N=3\) и на табличках представлены слова 'box', 'cat', 'car', коровам нужно как минимум 1 'b', 1 'o', 1 'x', 2 'c', 2 'a', 1 't', 1 'r'.

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

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

Определите максимальное количество комнат, в которые Беси может включить свет.

ПРИМЕР ВЫВОДА

5

Здесь Беси может использовать переключатель в комнате \((1,1)\), чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где она может включить свет в комнате \((2,2)\). Переключатель в комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.

Авторы: Austin Bannister и Brian Dean

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

Определите максимальное количество комнат, в которые Беси может включить свет.

ПРИМЕР ВЫВОДА

5

Здесь Беси может использовать переключатель в комнате \((1,1)\), чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где она может включить свет в комнате \((2,2)\). Переключатель в комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.

Авторы: Austin Bannister и Brian Dean

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

ФД проталкивает молоко между K парами стойл (\(1 \leq K \leq 100,000\)). Для \(i\)-ой такой пары вам сообщают \(s_i\) и \(t_i\), начальную и конечную точки пути между которыми молоко проталкивается на единичной скорости. ФД опасается, что некоторые стойла могут переполниться молоком, проталкиваемым через них. Помогите ФД определить максимальное количество молока, которое можно протолкнуть через любое стойло. Если молоко проталкивается вдоль пути от \(s_i\) до \(t_i\), тогда считается, что оно проталкивается не только через конечные точки(стойла) \(s_i\) и \(t_i\), но также и через каждое стойло на пути между ними.

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