Информатика

У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).

Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через \(d\) дверей отнимает у неё \(d^2\) энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров, теперь им есть что почитать. К несчастью, последний номер содержит довольно неподходящую статью, как приготовить совершенный бифштекс. ФД хочет чтобы его коровы не увидели эту статью.

ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.

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

Формат входных данных

Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).

Формат выходных данных

Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.

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

Амбар описывается простым (несамопересекающимся) многоугольником с целочисленными вершинами \((x_1, y_1) \ldots (x_n, y_n)\) перечисленными в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y) отрезками. Первое ребро может быть как горизонтальным, так и вертикальным. Выход расположен в точке \((x_1, y_1)\). Беси начинает в некоторой вершине \((x_i, y_i)\) для \(i > 1\). Она идёт только по периметру амбара, по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения, в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода. Это довольно просто, когда свет включён - просто выбрать между движением по часовой стрелке и движением против часовой стрелки.

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

Помогите Беси определить минимальное количество, на которое возрастёт её путь в худшем случае при движении в темноте, по сравнению с движением при свете, полагая, что она движется оптимально в каждом случае. Оптимальная стратегия - такая, которая минимизирует увеличение расстояния в худшем случае.

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до \(\sqrt{X}\). То есть, квадрат расстояния между коровами стоит не более \(X\) чтобы обеспечить их коммуникацией.

Помогите коровам определить минимальное целое \(X\) такое, что сообщение от любой коровы сможет достичь любой другой коровы.

Этот сигнал состоит только из символов '.' и 'X'.

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

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

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

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

Беси сортирует массив целых чисел собственным алгоритмом. У неё есть куча из \(N\) \((1 \leq N \leq 2\cdot 10^5)\) целых чисел \(a_1,a_2,\dots,a_N\) \((1 \leq a_i \leq 10^{11})\), которые она хочет перенести в другой массив в отсортированном порядке. Она постоянно ищет минимальный элемент в куче, удаляет его и добавляет в конец массива. Беси требуется \(p\) секунд, чтобы найти минимальный элемент в куче из \(p\) целых чисел.

ФД выделил Беси в помощь неограниченное количество коров. Беси использует их следующим образом. Она разделила все свои целые числа на две кучи: куча Беси и куча Помощниц. Для каждого числа в своей куче она выполняет алгоритм как обычно. Для каждого целого числа в куче Помощниц Беси назначает его отдельной корове. И предлагает ей поступать так. Когда корова помощница получает число \(a_i\), она должна подождать \(a_i\) секунд и затем добавить это число в конец массива. Если Беси и корова-помощница добавляют число в одно и то же время, то сначала добавляется число Беси. Если нескольким коровам-помощницам было дано одно и то же число, они добавляют копии этого числа в одно и то же время.

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

У Фермера Джона важная задача - решить какой тип сена купить для своих коров.

У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)). ФД хочет, чтобы все его коровы любили один тип сена.

Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в фокус-группе более половины коров любит один и тот же некоторый тип сена, то все коровы начинают любить этот тип сена, иначе ни у одной коровы не изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров, 9 или более из которых любят один и тот же тип сена, то и остальные 7 коров теперь будут любить этот же тип сена.

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

Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет \(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.

После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\) шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть. Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только \(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\) ходов прежде, чем Беси надоест, и она перестанет играть. Можете ли Вы определить лексикографически минимальную последовательность ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.