Алгоритмы

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

ФД хочет кормить своих коров пока у всех у них не станет один и тот же уровень голода - целый, неотрицательный. Хотя он не знает точно уровень голода каждой из своих коров, он знает верхнюю границу уровня голода каждой коровы, то есть уровень голода \(i\)-ой cow \(h_i\) не более \(H_i\) (\(0\le H_i\le 1000\)).

Ваша задача - посчитать по модулю \(10^9+7\) количество комбинаций из \(N\) уровней голода \([h_1,h_2,\ldots,h_N]\) таких, что ФД сможет достичь своей цели.

Рассмотрим 4-гранные кости

Кость A имеет числа 4, 5, 6, 7 на своих гранях.

Кость B имеет числа 2, 4, 5, 10 на своих гранях.

Кость C имеет числа 1, 4, 8, 9 на своих гранях.

Эти кости удовлетворяют довольно интересному свойству: A бьёт B, B бьёт C, C бьёт A. В частности, ни одна из этих костей не является "наилучшей", бьющёй две других. В этом случае, когда ни одна из трёх костей не является "наилучшей" и нет двух костей с олинаковой вероятностью победить, мы называем множество из таких трёх костей "не-транзитивным".

Вам дали числа на гранях двух 4-гранных костей A и B. Помогите коровам определить, есть ли способ назначить числа на гранях третьей кости С так, чтобы множество стало "не-транзитивным". Числа на всех гранях всех костей - целые в интервале от 1 до 10 включительно.

\(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона выстроены в ряд так, что \(i\)-ая корова в этому ряду имеет уровень голода \(h_i\) (\(0 \leq h_i \leq 10^9\)). Поскольку коровы - социальные животные и хотят есть вместе, единственный способ уменьшить уровень голода его коров - выбрать двух соседних коров с номерами \(i\) и \(i+1\) и скормить каждой из них по мешку кукурузы, чтобы уменьшить уровень голода каждой из них на один.

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

Заметим что требуется использовать 64-битное целое для ответа (например "long long" в C/C++)

Экран ФД небольшой, поэтому он может видеть одновременно \(K\) (\(1\le K\le \min(N,M)\)) папок и \(K\) писем одновременно. Изначально, его экран показывает папки \(1 \ldots K\) слева и письма \(1 \ldots K\) справа. Для того чтобы увидеть другие папки и письма, он должен скроллить соответствующие списки. Например, если он проскроллит вниз на одну позицию в списке папок, он увидит папки \(2 \ldots K+1\), а если проскроллит ещё на одну позицию вниз, он увидит папки \(3 \ldots K+2\). Когда ФД переносит письмо в папку, оно исчезает из списка писем, и все нижние письма поднимаются на одну позицию вверх. Например, пусть на экране отображены письма \(1, 2, 3, 4, 5\) и ФД переносит письмо 3 в соответствующую папку, тогда видимая часть списка писем станет такой: \(1, 2, 4, 5, 6\). ФД может переносить письма только в назначенные им папки.

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

Помогите ФД определить, может ли он разнести по папкам все свои письма.

\(i\)-ая корова размещена в точке \((x_i,y_i)\), где \(0 \leq x_i \leq 10^6\) \(0 \leq y_i \leq 10\). Стоимость построения коммуникационной линии между коровами \(i\) и \(j\) есть квадрат расстояния между ними: \((x_i-x_j)^2 + (y_i-y_j)^2\).

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

**Замечание : Лимитна время на тест = 4s, в дфа раза больше обычного..**

ФД это заметил и попросил Эльзу вести учёт засыпаний Беси. Всего имеется \(N\) (\(1\le N\le 10^5\)) периодов, когда проходили занятия. И Эльза записала, что Беси засыпала \(a_i\) (\(0\le a_i\le 10^6\)) раз во время \(i\)-го периода. Общее количество засыпаний Беси не превышает \(10^6\).

Эльза хочет показать ФД, что Беси всегда засыпала одинаковое количество раз. Но единственный способ, которым она это может сделать - объединить два соседних периода проведения занятий. Например, если \(a=[1,2,3,4,5],\) то Эльза может объединить второй и третий периоды и лог станет таким \([1,5,4,5]\).

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

Изначально коровы выстроились в порядке \(a_1,a_2,\ldots,a_N\) слева направо. Цель ФД выстроить их в порядке \(b_1,\ldots,b_N\) слева направо. Чтобы достичь своей цели, ФД может выполнить несколько модификаций порядка. Каждая модификация состоит в том, чтобы выбрать корову и переместить её влево на некоторое количество позиций.

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

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

Имеется \(N\) (\(1 \leq N \leq 2000\)) гор в ряд на ферме Джона Это может быть выражено как массив высот \(h_1,h_2,\dots,h_N\). Для горы \(i\), Вы можете увидеть другую гору \(j\) если нет гор строго выше чем линия взгляда, соединяющая горы \(j\) и \(i\). Формально, для двух гор \(i < j\), они могут видеть друг друга, если не существует такого \(k\) \(i < k < j\) и \((k, h_k)\) выше чем отрезок, соединяющий \((i, h_i)\) и \((j, h_j)\). Имеется \(Q\) (\(1 \leq Q \leq 2000\)) изменений высот, когда высота одной горы возрастает. Определите общее количество неупорядоченных пар гор, которые могут видеть друг друга после каждого изменения.

ПРМЕР ВВОДА:

5
2 4 3 1 5
3
4 3
1 3
3 2

У Беси \(N\) (\(1 \le N \le 2000\)) друзей. Однако они разные! Друг \(i\) имеет счёт популярности \(P_i\) (\(1 \le P_i \le 2000\)), и Беси хочет максимизировать сумму популярности друзей, которые пойдут с ней. Друг \(i\) пойдёт с ней только если она даст ему \(C_i\) (\(1 \le C_i \le 2000\)) "moonies". Друг \(i\) также может сделать скидку в \(1\) "mooney", если она даст ему \(X_i\) (\(1 \le X_i \le 2000\)) мороженых. Беси может получить сколько угодно скидок.

У Беси есть \(A\) moonies и \(B\) мороженых (\(0 \le A, B \le 2000\)). Помогите ей определить максимальную сумму популярностей, которую она может добиться, если потратит mooney и мороженое оптмально.

Поскольку все коровы голодные, ФД решил выложить пакты с травой в некоторых позициях \(1\dots N\). Коровы разных пород едят разные типы травы. Каждый пакет травы должен содержать траву только одного типа (для G или для H). Он не может разместить пакеты с разной травой в одной и той же позиции. Каждый пакет травы может накормить неограниченное количество коров соответствующего типа.

Каждая корова готова пройти не более \(K\) (\(0 \le {K} \le N-1\)) позиций чтобы добраться до пакета с травой. Определите минимальное количество пакетов с травой, необходимое чтобы накормить всех коров. Любая конфигурация, удовлетворяющая указанным выше ограничениям, будет рассматриваться как корректная.

Имеется \(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\).