Информатика

Имеется \(N\) (\(1 \le N \le 10^5\)) коров, которые потенциально могут посещать университет. Каждая корова готова платить за обучение максимум \(c_i\) (\(1 \le c_i \le 10^6\)). Фермер Джон может установить плату за обучение, которую все коровы должны оплатить. Если эта плата больше, чем корова готова платить, она не платит и не учится в университете. Фермер Джон хочет установить такую оплату, чтобы получить максимальную сумм оплат. Определите эту максимальную сумму и установленную плату за обучение.

Сейчас Эльза создаёт новый неориентированный граф \(G\) с \(N_1\cdot N_2\cdots N_K\) вершинами, каждая из которых помечена \(K\)-плетом \((j_1,j_2,\ldots,j_K)\), где \(1\le j_i\le N_i\). В \(G\) две вершины \((j_1,j_2,\ldots,j_K)\) и \((k_1,k_2,\ldots,k_K)\) соединены ребром, если для всех i \(1\le i\le K\), \(j_i\) и \(k_i\) соединены ребром в \(G_i\).

Определим расстояние между двумя вершинами в \(G\) которые лежат в одной и той же связной компоненте как минимальное количество ребер на пути из одной вершины в другую. Вычислите сумму расстояний между вершиной \((1,1,\ldots,1)\) и каждой вершиной в этой же компоненте в \(G\) по модулю \(10^9+7\).

Беси начинает в ячейке \((1,1)\). Если она находится в ячейке \((x,y)\), она может выполнить одно из следующих действий:

• Если \(y<M\), Беси может переместиться в следующую колонку (увеличивая \(y\) на 1) за цену \(x^2\).
• Если \(x<N\), Беси может переместиться в следующую строку (увеличивая \(x\) на 1) за цену \(c_y\).

ВАм даются \(Q\) (\(1\le Q\le 2\cdot 10^5\)) независимых запросов, каждый в виде \((x_i,y_i)\) (\(x_i\in [1,N], y_i\in [1,M]\)), вычислите минимально возможную цену для Беси переместиться из \((1,1)\) в \((x_i,y_i)\). compute the minimum possible total

Коротая время, Милдред бормочет cowphabet опять и опять. Фермер Нхой хочет узнать, сколько раз она пробормотала cowphabet.

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

Замечание: время на тест для этой задачи удвоено.

\(|i-j|\) минут требуется, чтобы передать сообщение от коровы \(i\) к корове \(j\). Однако не все породы готовы взаимодействовать друг с другом, что описано в матрице \(S\) размером \(K \times K\), где \(S_{ij} = 1\) если корова породы \(i\) готова передать сообщение корове породы \(j\) и 0 в противном случае. Необязательно истина то, что \(S_{ij}=S_{ji}\), и даже может быть случай, когда \(S_{ii} = 0\), то есть корова породы \(i\) не будет передавать сообщение корове своей породы.

Определите минимальное количество времени, которое потребуется для передачи сообщения.

Чтобы играть в эту игру, Беси выбирает некоторый интервал, например \(i\)-ый. И Эльза выбирает некоторый интервал, например, \(j\)-ый, возможно тот же самый. Для заданной величины \(k\) они выигрывают, если \(a_i + a_j \leq k \leq b_i + b_j\).

Для всех \(k\) в интервале \(0 \ldots 2M\), посчитайте количество упорядоченных пар \((i,j)\) для которых Беси и Эльза выиграют в эту игру.

На этой ферме имеется два амбара - один в поле \(1\), другой в поле \(N\). ФД хочет быть уверен, что имеется путь между двумя амбарами последовательностью дорожек. Оно готов построить до двух новых дорожек, чтобы добиться своей цели. Стоимость построения дорожки между полями \(i\) и \(j\) есть \((i-j)^2\).

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

ФД хочет выбрать \(N\) (\(1\le N\le 2\cdot 10^5\)) (не обязательно в целых числах) для размещения своих коров. Эти числа должны отличаться от позиций занимаемых коровами ФН, но они могут находится в позициях травяных пастбищ.

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

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

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

• Каждая пара состоит из двух различных коров \(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\).