Информатика

Каждый день они выпускают новый пазл. Пазл представляет собой решётку 3*3, гже каждая клетка занята коровой определённой породы. Всего имеется 26 различных видов пород, которые представляются большими латинским буквами от A до Z. Играющий должен узнать тип породы в каждой клетке через серию запросов. В каждом запросе от представляет 3*3 латинских букв. Ответ формируется следующим образом: если буквы угаданы, они подсвечиваются зелёным, Буквы верной породы, но не на своём месте подсвечиваются жёлтым.

Количество подсвеченных указывает, сколько их должно быть. Например, предположим, что гипотеза содержит 4 символа A, а правильный ответ содержит только 2 символа A, причём ни одна позиция не угадана. Тогда в ответе на этот запрос только 2 символа A будут подсвечены жёлтым. В общем случае, если \(x\) коров определённой породы в запросе и только \(y\) - в правильном ответе (не считая коров, которые уже стоят на своём месте и будут подсвечены зелёным), только \(y\) из этих \(x\) коров будут подсвечены жёлтым.

По заданным правильному ответу и запросу вычислите количество квадратов, подсвеченных зелёным цветом и количество квадратов, подсвеченных жёлтым цветом.

\(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 и мороженое оптмально.

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

Например, если ввод в эту программу есть "10" (то есть, \(b[0] = 1\) и \(b[1] = 0\)), тогда вывод должен быть 1

Эльза должна сказать правильный ответ для \(M\) (\(1\le M\le 100\)) различных вводов. Бесси сейчас пытается сделать "реверс инжиниринг" для программы Эльзы. К несчастью, Эльза может и солгать - то есть не существует программы вида указанного выше, которая выведет ответы как сказала Эльза.

Для каждого из \(T\) (\(1\le T\le 10\)) подтестов определит, лгала Эльза или нет.

Поскольку все коровы голодные, ФД решил выложить пакты с травой в некоторых позициях \(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\).

Беси начинает в ячейке \((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\)) (не обязательно в целых числах) для размещения своих коров. Эти числа должны отличаться от позиций занимаемых коровами ФН, но они могут находится в позициях травяных пастбищ.

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

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