Алгоритмы

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

Беси начинает в комнате \((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\), но также и через каждое стойло на пути между ними.

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

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

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

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

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

• Если клетка red (красная), то в неё ходить нельзя
• Если клетка pink (розовая), то в неё можно ходить
• Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
• Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
• Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

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

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

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

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

• Если клетка red (красная), то в неё ходить нельзя
• Если клетка pink (розовая), то в неё можно ходить
• Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
• Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
• Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

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

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

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

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

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