Информатика

По сигналу Фермера Джона некоторые из коров формируют пары так, что

• Каждая пара состоит из двух различных коров \(a\) и \(b\) чьи расположения не далее \(K\) друг от друга (\(1\le K\le 10^9\)); то есть \(|x_a-x_b|\le K\).
• Каждая корова или является частью некоторой пары или не является частью некоторой пары.
• Группировка в пары называется максимальной, если никакие две из неспаренных коров не могут образовать пары.

  Определите интервал возможных сумм весов неспаренных коров. А именно

  • Если \(T=1\), вычислите минимально возможную сумму весов неспаренных коров.
  • Если \(T=2\), вычислите максимально возможную сумму весов неспаренных коров.

  ФОРМАТ ВВОДА (с клавиатуры / stdin):

  Первая строка ввода содержит \(T\), \(N\), \(K\).

  В каждой из последующих \(N\) строк \(i\)-ая строка содержит \(x_i\) и \(y_i\). Гарантируется, что \(0\le x_1< x_2< \cdots< x_N\le 10^9\)

  ФОРМАТ ВЫВОДА (на экран / stdout):

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

Пастбище и амбар расположены на решётке \(N \times N\) (\(2 \leq N \leq 50\)), причём пастбище находится в левом верхнем углу, а амбар - в правом нижнем. Беси хочет попасть в амбар как можно быстрее, поэтому она ходит только вниз и вправо. В некоторых ячейках находятся стоги сена, которые Беси должна обходить.

Беси чувствует себя уставшей, поэтому она хочет изменить направление движения не более \(K\) раз (\(1 \leq K \leq 3\)).

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

Эти коровы сейчас стоят в ряд и ФД хочет сделать фото каждой последовательности из трёх или более последовательных коров. Однако он не хочет делать фото, в котором ровно одна корова породы Guernsey или ровно одна корова породы Holstein --- он считает, что эта одна корова будет чувствовать себя изолированной. После взятия фото каждой последовательности из трёх или более коров, он выбрасывает так называемые "одинокие" фото, на которых ровно одна корова породы Guernsey или ровно одна корова породы Holstein.

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

Амабар Фермера Джона содержит последовательность из \(N\) стойл, пронумерованных \(1 \ldots N\), каждое содержит ровно одну корову. \(i\)-ая корова предпочитает, чтобы температура в её стойле была \(p_i\), а прямо сейчас температура в её стойле \(t_i\). Для того чтобы угодить всем коровам, ФД установил новую систему кондиционирования, которая работает следующим образом. ФД посылает команды системе - увеличить или уменьшить температуру в некоторых подряд идущих стойлах на 1 (например, увеличить на 1 температуру в стойлах \(5 \ldots 8\)). Последовательность стойл может состоять из одного стойла.

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

Разбрызгиватель для пшеницы в квадрате \((I,J)\) разбрызгивает на все квадраты ниже и слева: то есть, квадраты \((i,j)\) с \(I \le i\) и \(j \le J\).

Разбрызгиватель для люцерны в квадрате \((I,J)\) разбрызгивает на все квадраты вверху и справа: то есть, квадраты \((i,j)\) с \(i \le I\) b \(J \le j\).

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

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

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

Для каждого \(j=0,1,\ldots,N-1\), ФД хочет узнать "негодность" его волос если все пряди с длиной больше чем \(j\) будут уменьшены до длины ровно \(j\).

\(N\) коров (\(1\le N\le 10^4\)) стоят в ряд. \(i\)-ая корова слева имеет метку \(i\) для каждого \(1\le i\le N\). ФД говорит коровам повторять следующие действия до тех пор, пока коровы не вернуться к тому же порядку, с которого начинали:

• По заданной перестановке \(A\) длины \(N\), коровы изменяют их порядок так, что \(i\)-ая корова слева до изменения становится \(A_i\) коровой слева после изменения

Например, если \(A=(1,2,3,4,5)\) тогда коровы выполнят один шаг. Если \(A=(2,3,1,5,4)\), тогда коровы выполнят 6 шагов. Порядок коров слева направо после каждого из шагов будет таким:

• 0 шаг: \((1,2,3,4,5)\)
• 1 шаг: \((3,1,2,5,4)\)
• 2 шаг: \((2,3,1,4,5)\)
• 3 шаг: \((1,2,3,5,4)\)
• 4 шаг: \((3,1,2,4,5)\)
• 5 шаг: \((2,3,1,5,4)\)
• 6 шаг: \((1,2,3,4,5)\)

Определите сумму всех положительных целых чисел \(K\) таких, что существует перестановка длины \(N\), которая требует от коров выполнить ровно \(K\) шагов.

Поскольку это число может быть очень большим, выведите ответ по модулю \(M\) (\(10^8\le M\le 10^9+7\), \(M\) - простое).

Беси хочет максимизировать количество ягод, которое она соберёт. Однако ФД хочет, чтоб Беси поделилась ягодами со своей младшей сестрой, поэтому Беси должна отдать Эльзе \(K/2\) корзин с наибольшим количеством ягод. Это значит, что у Эльзы может даже оказаться больше ягод чем у Беси.

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

Эссе содержит \(N\) слов (\(1\le N\le 100\)), разделённых пробелами. Каждое слово имеет длину от 1 до 15 символов включительно, и состоит только из больших или маленьких латинских букв. В соответствии с правилами, эссе должно быть отформатировано специфическим образом: каждая строк должна содержать не более \(K\) (\(1\le K\le 80\)) символов, не считая пробелы. К счастью, текстовый процессор Беси может выполнять это требование при использовании следующей стратегии:

• Если Беси пишет слово которое может поместится на текущей строке, оно помещается в эту строку.
• Иначе надо переместить слово в следующую строку и продолжить пополнение этой следующей строки.

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

К несчастью, текстовый процессор Беси сломался, помогите ей отформатировать её эссе в соответствии с вышеописанными правилами.

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

Однако, ФД сможет восстановить перестановку, которую он изначально выписал. Перед тем, как листок с перестановкой был украден, Беси выписала последовательность \(b_1,b_2,\ldots,b_{N-1}\) такую, что \(b_i=a_i+a_{i+1}\) для всех \(1\le i<N.\)

Основываясь на информации от Беси, помогите ФД восстановить "лексикографически минимальную" перестановку \(a\), которая может произвести \(b\). Перестановка \(x\) лексикографически меньше перестановки \(y\), если для некоторого \(j\), \(x_i=y_i\) для всех \(i<j\) и \(x_j<y_j\) (другими словами, две перестановки идентичны до определённой точки, в которой \(x\) меньше чем \(y\)). Гарантируется, что существует как минимум одна такая перестановка \(a\)

ФД хочет разбить множество дорог на несколько путей. Его не беспокоит количество путей. Однако он хочет чтобы все эти пути максимально возможными.

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

Определите объединение отрезов, которое будет множеством всех \(x\) которые содержатся внутри хотя бы одного отрезка. также определите сложность множества отрезков как количество связанных отрезков, представленных в этом объединении.

Беси хочет вычислить сумму сложностей во всем \(2^N\) подмножествам заданного множества из \(N\) отрезков по модулю \(10^9+7\).

Помогите Беси!

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

Более точно для каждого \(1 \leq K \leq N-1\), помогите ФД определить, могут ли дороги быть распределены на пути длиной ровно \(K\).

Каждый час корова или

• Останавливается, если трава в текущей ячейке уже съедена другой коровой.
• Съедает всю траву в текущей ячейке и перемещается на одну ячейку вперёд в своём исходном направлении.

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

Если две коровы попадут одновременно на одну и ту же ячейку с травой, они поедят вместе и продолжат движение в своих направлениях в следующий час.

ФД не любит, когда корова прекращает пастись, и он хочет узнать, кто виноват в его остановленных коровах. Если корова \(b\) остановилась в ячейке, которую съела корова \(a\), тогда он считает, что корова \(a\) остановила корову \(b\). Более того, если корова \(a\) остановила корову \(b\), а корова \(b\) остановила корову \(c\), он считает, что корова \(a\) также остановила корову \(c\) (то есть отношение "остановила" транзитивно). Каждая корова "виновата" в количестве коров, которые она остановила. Для каждой коровы вычислите количество остановленных ею коров.

Чтобы было понятнее относительно направлений и координат, если корова в ячейке \((x,y)\) и двигается на север, то она попадёт в ячейку \((x,y+1)\), а если на восток - то в ячейку \((x+1, y)\).

ФД начинает с одного генома и редактирует его, выполняя следующие шаги:

1. Разделяет геном между каждыми двумя последовательными равными символами.
2. Реверсирует каждую из полученных подстрок.
3. Конкатенирует реверсированные подстроки в том же порядке.

Например, если ФД начинает с генома AGGCTTT, то он выполнит следующие шаги:

1. Разделит между последовательными равными символами G и T получит AG | GCT | T | T.
2. Реверсирует каждую подстроку, получит GA | TCG | T | T.
3. Конкатенирует реверсированные подстроки, получит GATCGTT.

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

По заданной последовательности отредактированного генома помогите ФД определить количество возможностей для стартового генома по модулю \(10^9+7\).

У Элзи есть три положительных целых числа \(A\), \(B\), \(C\) (\(A\le B\le C\)). Эти целые числа предполагаются как секретные, поэтому она не говорит их своей сестре Беси. Вместо этого, она говорит Беси семь необязательно различных целых чисел в интервале \(1 \ldots 10^9\), подсказывая, что они есть \(A\), \(B\), \(C\), \(A+B\), \(B+C\), \(C+A\), \(A+B+C\) в некотором порядке.

По заданному списку из этих 7 чисел, помогите Беси определить \(A\), \(B\), \(C\). Можно доказать, что ответ уникален.

Как подающий надежды фотограф, Беси решила сделать несколько фото этих цветков. В частности, для каждой пары цветков \((i,j)\) где \(1\le i\le j\le N\), Беси делает фото всех цветков от \(i\) до \(j\) (включая \(i\) и \(j\)).

Затем Беси посмотрела на эти фотки и заметила, что некоторые фото имеют "средний цветок" - цветок, который имеет \(P\) лепестков, где \(P\) - точное среднее число лепестков среди всех цветков на этом фото.

Сколько из фотографий Беси имеют "средний цветок"?

На этот раз он делает фото с воздуха. Он хочет, чтоб все его коровы смотрели в одну сторону. Сейчас коровы организованы в решётку \(N \times N\), (\(2 \leq N \leq 1000\)) внутри квадратного пастбища, как показано ниже:

RLR
RRL
LLR

Здесь 'R' означает, что корова смотри вправо, 'L' означает, что корова смотрит влево. Поскольку коровы находятся в стаде, ФД не может говорить повернуться одной корове. Всё что он может - это повернуть целую строку или целый столбец повернув коров 'L' на 'R' или 'R' на 'L' внутри этой строки/столбца. ФД может поворачивать столбцы и строки сколько угодно раз, в том числе и поворачивать один тот же столбец или строку более чем один раз.

Как оказалось, ФД не может перевернуть всех коров в одном направлении, Но может всех коров кроме одной - определите эту корову.

Каждая корова расположена в точке \((x,y)\) на двумерной карте фермы. И нам известны \(M\) (\((1 \leq M < 10^5)\)) пар коров, принадлежащих к одной и той же группе.

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